Tutte’s Theorem by Induction

The Induction Strategy

Tutte’s theorem characterizes exactly when a finite graph has a perfect matching. Its condition counts the odd components left after deleting a set of vertices. The necessity of the condition follows by looking at how a perfect matching must cover those components. The sufficiency direction is harder: induction must handle both a set where the condition is tight and the case where every relevant inequality is strict.

All graphs in this tutorial are finite and simple. A matching is a set of edges no two of which share a vertex. It is perfect if every vertex is incident with one of its edges. A component is a maximal connected subgraph. For a graph \(G\) and a vertex set \(S\subseteq V(G)\), \(G-S\) means the subgraph induced by the vertices not in \(S\). Write \(o(G-S)\) for the number of components of \(G-S\) that have odd order. The empty graph has zero components, so \(o(G)=0\) when \(G\) has no vertices.

Singleton tight sets are deliberately excluded from the phrase “nontrivial tight set.” In an even-order graph satisfying Tutte’s condition, deleting one vertex leaves an odd number of vertices, so the number of odd components is at least one and at most one. Thus singleton tight sets can occur routinely; they do not obstruct the edge-deletion step used in the induction.

Tutte’s Theorem

Proof of necessity. Suppose \(G\) has a perfect matching \(M\), and fix \(S\subseteq V(G)\). Each odd component of \(G-S\) must have at least one vertex whose matching edge goes from that component to a vertex of \(S\): otherwise all vertices of the component would have to be matched to one another, which is impossible for an odd number of vertices. Different components require different vertices of \(S\), because \(M\) is a matching. Therefore \(o(G-S)\le |S|\). This also covers \(S=\varnothing\): a graph with a perfect matching has no odd component. \(\square\)

For sufficiency, we use induction on \(n=|V(G)|\), proving that every graph satisfying Tutte’s condition has a perfect matching. At \(n=0\), the empty matching is perfect, and the condition holds. If the condition holds at \(S=\varnothing\), then \(o(G)=0\); hence every component has even order and \(n\) is even. In particular, a graph of order one cannot satisfy the condition.

We will use the following earlier result, the Tight-Set Reduction Lemma. Its hypotheses are that \(G\) satisfies Tutte’s condition and \(S\) is a nonempty proper tight set. It gives a matching decomposition: the even components of \(G-S\) can be matched internally, and the odd components can be matched to distinct vertices of \(S\), using one edge from \(S\) into each such component and matching the remaining vertices of that component internally. The reduction lemma is the step that handles tight sets; it does not require each odd component of \(G-S\) to be factor-critical.

That last qualification matters. An odd component need not have a perfect matching after deletion of every possible vertex. The reduction lemma selects the vertices and edges together, so it only needs internal matchings after the particular vertices used to meet \(S\) have been selected. Since \(S\) is tight, the number of odd components is exactly \(|S|\), just the number needed in this matching decomposition.

Disconnected Graphs and the Tight-Set Case

Suppose first that \(G\) is disconnected. For any component \(H\) of \(G\) and any \(X\subseteq V(H)\), the odd components of \(H-X\) are among the odd components of \(G-X\). Therefore \(o(H-X)\le o(G-X)\le |X|\), so \(H\) itself satisfies Tutte’s condition. Also, each component of \(G\) has even order: at \(S=\varnothing\), the condition says \(o(G)=0\). Every component has fewer than \(n\) vertices, so induction gives a perfect matching in each component. Their union is a perfect matching of \(G\).

It remains to consider connected \(G\). If there is a nontrivial tight set \(S\), then \(S\) is nonempty and proper, and the Tight-Set Reduction Lemma applies. Its matching decomposition covers every vertex of \(S\), every odd component of \(G-S\), and every even component of \(G-S\). Combining the edges it supplies gives a perfect matching of \(G\).

This accounts for the tight-set case without making an unwarranted claim about every vertex of an odd component. The induction still has to address the case in which there is no nontrivial tight set; that case uses a different reduction.

The Case with No Nontrivial Tight Set

Assume \(G\) is connected and satisfies Tutte’s condition, and suppose it has no nontrivial tight set. The order \(n\) is even and at least two, so connectedness guarantees an edge \(uv\). We will show that \(G-\{u,v\}\) satisfies Tutte’s condition. Induction will then give a perfect matching of that smaller graph; adding \(uv\) will complete the matching of \(G\).

Here is the parity fact that makes the argument work. For any vertex set \(T\), the sum of the orders of the components of \(G-T\) is \(n-|T|\). Modulo \(2\), that sum has the same parity as the number of odd components. Since \(n\) is even, this gives \(o(G-T)\equiv |T|\pmod 2\). Consequently, if \(2\le |T|\le n-1\), Tutte’s condition and the absence of nontrivial tight sets imply \(o(G-T)\le |T|-2\): the inequality is strict, and both sides have the same parity.

Now let \(X\subseteq V(G)\setminus\{u,v\}\), and set \(T=X\cup\{u,v\}\). If \(T=V(G)\), then \(G-T\) is empty and \(o(G-T)=0\le |X|\). Otherwise \(2\le |T|\le n-1\), so the parity bound gives \(o(G-T)\le |T|-2=|X|\). Since \(G-\{u,v\}-X=G-T\), this is exactly the condition required for \(G-\{u,v\}\).

The graph \(G-\{u,v\}\) has \(n-2<n\) vertices, so the induction hypothesis provides a perfect matching \(M\) in it. The edge \(uv\) has neither endpoint in that smaller graph. Therefore \(M\cup\{uv\}\) is a matching, and it covers every vertex of \(G\). This proves sufficiency and completes the induction. \(\square\)

Why the Strict Inequality Is Essential

In the edge-deletion step, the set tested in the original graph is \(T=X\cup\{u,v\}\). When \(X\) is nonempty, the desired upper bound is not merely \(o(G-T)\le |T|\); it is \(o(G-T)\le |T|-2\). The missing two account exactly for the two deleted vertices \(u\) and \(v\). Parity turns strictness into this two-unit improvement. If \(T\) were tight, this argument would not establish the condition for the smaller graph. That is why tight sets and the no-tight-set case require different steps.

A related common mistake is to call every tight set “nontrivial” and then assume strictness for all nonempty \(T\). That is false even in \(K_4\): every singleton \(T\) is tight. The induction only needs strictness for sets of size at least two, because every tested set \(T=X\cup\{u,v\}\) has at least two vertices. Empty sets and the full vertex set are handled directly in the proof.