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 \(\max_{X \subseteq V(G)} \{ \omega_0(G – X) – |X| \}\) of \(G\), where \(\omega_0(H)\) denotes the number of odd components of \(H\). Let \(G’\) 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’\).