The theorem states that the size of a maximum matching of a graph equals where counts how many of the connected components of the graph have an odd number of vertices.
Explanation
Intuitively, for any subset U of the vertices, the only way to completely cover an odd component of G − U by a matching is for one of the matched edges covering the component to be incident to U. If, instead, some odd component had no matched edge connecting it to U, then the part of the matching that covered the component would cover its vertices in pairs, but since the component has an odd number of vertices it would necessarily include at least one leftover and unmatched vertex. Therefore, if some choice of U has few vertices but its removal creates a large number of odd components, then there will be many unmatched vertices, implying that the matching itself will be small. This reasoning can be made precise by stating that the size of a maximum matching is at most equal to the value given by the Tutte–Berge formula. The characterization of Tutte and Berge proves that this is the only obstacle to creating a large matching: the size of the optimal matching will be determined by the subset U with the biggest difference between its numbers of odd components outside U and vertices inside U. That is, there always exists a subset U such that deleting U creates the correct number of odd components needed to make the formula true. One way to find such a set U is to choose any maximum matching M, and to letX be the set of vertices that are either unmatched in M, or that can be reached from an unmatched vertex by an alternating path that ends with a matched edge. Then, letU be the set of vertices that are matched by M to vertices in X. No two vertices in X can be adjacent, for if they were then their alternating paths could be concatenated to give a path by which the matching could be increased, contradicting the maximality of M. Every neighbor of a vertex x in X must belong to U, for otherwise we could extend an alternating path to x by one more pair of edges, through the neighbor, causing the neighbor to become part of U. Therefore, in G − U, every vertex of X forms a single-vertex component, which is odd. There can be no other odd components, because all other vertices remain matched after deleting U. So with this construction the size of U and the number of odd components created by deleting U are what they need to be to make the formula be true.
characterizes the graphs with perfect matchings as being the ones for which deleting any subset U of vertices creates at most |U| odd components. In this case, by the Tutte–Berge formula, the size of the matching is |V|/2; that is, the maximum matching is a perfect matching. Thus, Tutte's theorem can be derived as a corollary of the Tutte–Berge formula, and the formula can be seen as a generalization of Tutte's theorem.
