Subdivision of Edges and Matching Size

Abstract

The well-known formula of Tutte and Berge expresses the size of a maximum matching in a graph $G$ in terms of the deficiency $\underset{X\subseteq V(G)}{max}\{{\omega }_0(G–X)–|X|\}$ of $G$, where ${\omega }_0(H)$ denotes the number of odd components of $H$. Let $G^{\prime }$ be the graph formed from $G$ by subdividing (possibly repeatedly) a number of its edges. In this note we study the effect such subdivisions have on the difference between the size of a maximum matching in $G$ and the size of a maximum matching in $G^{\prime }$.