Tutte theorem
In the mathematical discipline of graph theory, the Tutte theorem, named after William Thomas Tutte, is a characterization of finite undirected graphs with perfect matchings.
The goal is to characterize all graphs that do not have a perfect matching.
Start with the most obvious case of a graph without a perfect matching: a graph with an odd number of vertices.
In such a graph, any matching leaves at least one unmatched vertex, so it cannot be perfect.
A slightly more general case is a disconnected graph in which one or more components have an odd number of vertices (even if the total number of vertices is even).
Therefore, any matching leaves at least one unmatched vertex in every odd component, so it cannot be perfect.
Next, consider a graph G with a vertex u such that, if we remove from G the vertex u and its adjacent edges, the remaining graph (denoted G − u) has two or more odd components.
Finally, consider a graph G with a set of vertices U such that, if we remove from G the vertices in U and all edges adjacent to them, the remaining graph (denoted G − U) has more than |U| odd components.
As explained above, any matching leaves at least one unmatched vertex in every odd component, and these can be matched only to vertices of U - but there are not enough vertices on U for all these unmatched vertices, so the matching is not perfect.
We have arrived at a necessary condition: if G has a perfect matching, then for every vertex subset U in G, the graph G − U has at most |U| odd components.
Tutte's theorem says that this condition is both necessary and sufficient for the existence of perfect matching.
A graph, G = (V, E), has a perfect matching if and only if for every subset U of V, the subgraph G − U has at most |U| odd components (connected components having an odd number of vertices).
denotes the number of odd components of the subgraph induced by
Necessity of (∗): This direction was already discussed in the section Intuition above, but let us sum up here the proof.
[2] Sufficiency of (∗): Let G be an arbitrary graph with no perfect matching.
We will find a so-called Tutte violator, that is, a subset S of V such that |S| < odd(G − S).
We can suppose that G is edge-maximal, i.e., G + e has a perfect matching for every edge e not present in G already.
Indeed, if we find a Tutte violator S in edge-maximal graph G, then S is also a Tutte violator in every spanning subgraph of G, as every odd component of G − S will be split into possibly more components at least one of which will again be odd.
Then S has to be a Tutte violator, since if odd(G − S) ≤ |S|, then we could find a perfect matching by matching one vertex from every odd component with a vertex from S and pairing up all other vertices (this will work unless |V| is odd, but then ∅ is a Tutte violator).
Now suppose that K is a component of G − S and x, y ∈ K are vertices such that xy ∉ E. Let x, a, b ∈ K be the first vertices on a shortest x,y-path in K. This ensures that xa, ab ∈ E and xb ∉ E. Since a ∉ S, there exists a vertex c such that ac ∉ E. From the edge-maximality of G, we define M1 as a perfect matching in G + xb and M2 as a perfect matching in G + ac.
Unless we arrive at 'special' vertices such as x, a or b, we can always continue: c is M2-matched by ca, so the first edge of P is not in M2, therefore the second vertex is M2-matched by a different edge and we continue in this manner.
If the last edge of P is in M2, then surely v ∈ {x, b} for analogous reason and we define C:=P + va + ac.
The Tutte–Berge formula says that the size of a maximum matching of a graph
Equivalently, the number of unmatched vertices in a maximum matching equals
For connected infinite graphs that are locally finite (every vertex has finite degree), a generalization of Tutte's condition holds: such graphs have perfect matchings if and only if there is no finite subset, the removal of which creates a number of finite odd components larger than the size of the subset.
