Tutte theorem

Example of a graph and one of its perfect matchings (in red).

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. It is a special case of the Tutte–Berge formula.

Intuition

An graph (or a component) with an odd number of vertices cannot have a perfect matching, since there will always be a vertex left alone.

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). Let us call such components odd components. In any matching, each vertex can only be matched to vertices in the same component. 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 Template:Math) has two or more odd components. As above, any matching leaves, in every odd component, at least one vertex that is unmatched to other vertices in the same component. Such a vertex can only be matched to u. But since there are two or more unmatched vertices, and only one of them can be matched to u, at least one other vertex remains unmatched, so the matching is not perfect.

Finally, consider a graph G with a set of vertices Template:Math such that, if we remove from G the vertices in Template:Math and all edges adjacent to them, the remaining graph (denoted Template:Math) has more than Template:Math 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 Template:Math - but there are not enough vertices on Template:Math 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 Template:Math in G, the graph Template:Math has at most Template:Math odd components. Tutte's theorem says that this condition is both necessary and sufficient for the existence of perfect matching.

Tutte's theorem

A graph, Template:Math, has a perfect matching if and only if for every subset Template:Math of Template:Math, the subgraph Template:Math has at most Template:Math odd components (connected components having an odd number of vertices).

Proof

First we write the condition:

$(*)\mathrm{\forall }U\subseteq V,odd(G-U)\le |U|$

where $odd(X)$ denotes the number of odd components of the subgraph induced by $X$.

Necessity of (∗): This direction was already discussed in the section Intuition above, but let us sum up here the proof. Consider a graph Template:Math, with a perfect matching. Let Template:Math be an arbitrary subset of Template:Math. Delete Template:Math. Let Template:Math be an arbitrary odd component in Template:Math. Since Template:Math had a perfect matching, at least one vertex in Template:Math must be matched to a vertex in Template:Math. Hence, each odd component has at least one vertex matched with a vertex in Template:Math. Since each vertex in Template:Math can be in this relation with at most one connected component (because of it being matched at most once in a perfect matching), Template:Math.

Sufficiency of (∗): Let Template:Math be an arbitrary graph with no perfect matching. We will find a so-called Tutte violator, that is, a subset Template:Math of Template:Math such that Template:Math. We can suppose that Template:Math is edge-maximal, i.e., Template:Math has a perfect matching for every edge Template:Math not present in Template:Math already. Indeed, if we find a Tutte violator Template:Math in edge-maximal graph Template:Math, then Template:Math is also a Tutte violator in every spanning subgraph of Template:Math, as every odd component of Template:Math will be split into possibly more components at least one of which will again be odd.

We define Template:Math to be the set of vertices with degree Template:Math. First we consider the case where all components of Template:Math are complete graphs. Then Template:Math has to be a Tutte violator, since if Template:Math, then we could find a perfect matching by matching one vertex from every odd component with a vertex from Template:Math and pairing up all other vertices (this will work unless Template:Math is odd, but then Template:Math is a Tutte violator).

Now suppose that Template:Math is a component of Template:Math and Template:Math are vertices such that Template:Math. Let Template:Math be the first vertices on a shortest Template:Math-path in Template:Math. This ensures that Template:Math and Template:Math. Since Template:Math, there exists a vertex Template:Math such that Template:Math. From the edge-maximality of Template:Math, we define Template:Math as a perfect matching in Template:Math and Template:Math as a perfect matching in Template:Math. Observe that surely Template:Math and Template:Math.

Let Template:Math be the maximal path in Template:Math that starts from Template:Math with an edge from Template:Math and whose edges alternate between Template:Math and Template:Math. How can Template:Math end? Unless we arrive at 'special' vertices such as Template:Math or Template:Math, we can always continue: Template:Math is Template:Math-matched by Template:Math, so the first edge of Template:Math is not in Template:Math, therefore the second vertex is Template:Math-matched by a different edge and we continue in this manner.

Let Template:Math denote the last vertex of Template:Math. If the last edge of Template:Math is in Template:Math, then Template:Math has to be Template:Math, since otherwise we could continue with an edge from Template:Math (even to arrive at Template:Math or Template:Math). In this case we define Template:Math. If the last edge of Template:Math is in Template:Math, then surely Template:Math} for analogous reason and we define Template:Math.

Now Template:Math is a cycle in Template:Math of even length with every other edge in Template:Math. We can now define Template:Math (where Template:Math is symmetric difference) and we obtain a perfect matching in Template:Math, a contradiction.

Equivalence to the Tutte-Berge formula

The Tutte–Berge formula says that the size of a maximum matching of a graph $G=(V,E)$ equals $\underset{U\subseteq V}{\min }(|U|-\mathrm{odd}(G-U)+|V|)/2$. Equivalently, the number of unmatched vertices in a maximum matching equals $\underset{U\subseteq V}{\max }(\mathrm{odd}(G-U)-|U|)$.

This formula follows from Tutte's theorem, together with the observation that $G$ has a matching of size $k$ if and only if the graph $G^{(k)}$ obtained by adding $|V|-2k$ new vertices, each joined to every original vertex of $G$, has a perfect matching. Since any set $X$ which separates $G^{(k)}$ into more than $|X|$ components must contain all the new vertices, (*) is satisfied for $G^{(k)}$ if and only if $k\le \underset{U\subseteq V}{\min }(|U|-\mathrm{odd}(G-U)+|V|)/2$.

In infinite graphs

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.

See also

• Bipartite matching
• Hall's marriage theorem
• Petersen's theorem

References

• Template:Cite book
• Template:Cite book