Using Tutte’s Condition as a Test
A perfect matching pairs every vertex with exactly one other vertex by an edge. In a small graph, finding such pairs may be straightforward, but showing that no such pairing exists can be less obvious. Tutte’s theorem gives a test: delete a set of vertices, count the odd components left behind, and compare that count with the size of the deleted set.
All graphs in this tutorial are finite and simple. A matching is a set of edges no two of which share an endpoint; it is perfect if every vertex is an endpoint of one of its edges. A component is a maximal connected subgraph. For \(S\subseteq V(G)\), \(G-S\) denotes the induced subgraph on \(V(G)\setminus S\). Write \(o(G-S)\) for the number of components of \(G-S\) that have an odd number of vertices. In particular, the graph with no vertices has zero components, so its odd-component count is zero.
The quantifier “for every” is essential. A set \(S\) with \(o(G-S)\le |S|\) does not establish that the graph has a perfect matching; some other set may violate the condition. By contrast, one strict inequality \(o(G-S)>|S|\) is enough to rule out a perfect matching.
Why a Violating Set Rules Out a Perfect Matching
Proof. Suppose that \(G\) has a perfect matching. Consider an odd component \(C\) of \(G-S\). The matching cannot pair all vertices of \(C\) using edges within \(C\), since every matching covers an even number of vertices and \(C\) has odd order. At least one vertex of \(C\) must therefore be matched to a vertex outside \(C\). There are no edges from \(C\) to another component of \(G-S\), so that matching edge must go to a vertex in \(S\). Distinct odd components require distinct vertices of \(S\), because a matching cannot use a vertex twice. It follows that \(o(G-S)\le |S|\), contrary to the assumed strict inequality. Thus \(G\) has no perfect matching. \(\square\)
This argument also explains how to read a violation: each odd component left after deletion needs a matching edge to the deleted set. If there are more such components than deleted vertices, there are not enough vertices available to supply those edges.
Worked Examples
Worked Example: A Six-Cycle Has a Perfect Matching
Let \(G=C_6\), with vertex set \(\{1,2,3,4,5,6\}\) and edge set \(\{12,23,34,45,56,61\}\). We verify Tutte’s condition for every \(S\), organizing the check by \(s=|S|\).
First take \(S=\varnothing\). The remaining graph is \(C_6\), one component of order \(6\), so \(o(G-S)=0\le 0\). Now suppose \(1\le s\le 5\). Deleting the vertices of \(S\) leaves runs of consecutive vertices along the cycle; each nonempty run is a path component. There are at most \(s\) such runs: each run is followed around the cycle by a deleted vertex, and distinct runs have distinct following deleted vertices. Thus the number of components, and hence the number of odd components, is at most \(s\). Also, there are \(6-s\) remaining vertices, so there can be at most \(6-s\) odd components. For \(s=6\), no vertices remain and \(o(G-S)=0\).
The resulting bounds, calculated for each possible size of \(S\), are:
| \(|S|=s\) | Remaining vertices \(6-s\) | Bound on \(o(G-S)\) | Required comparison |
|---|---|---|---|
| 0 | 6 | 0 (the whole cycle is even) | \(0\le 0\) |
| 1 | 5 | \(o(G-S)\le\min(1,5)=1\) | \(1\le 1\) |
| 2 | 4 | \(o(G-S)\le\min(2,4)=2\) | \(2\le 2\) |
| 3 | 3 | \(o(G-S)\le\min(3,3)=3\) | \(3\le 3\) |
| 4 | 2 | \(o(G-S)\le\min(4,2)=2\) | \(2\le 4\) |
| 5 | 1 | \(o(G-S)\le\min(5,1)=1\) | \(1\le 5\) |
| 6 | 0 | 0 | \(0\le 6\) |
In every row the bound on the odd-component count is at most \(s\), so the condition holds for every vertex set. A perfect matching is \(\{12,34,56\}\). Its edges are in \(E(G)\), share no endpoints, and cover all six vertices.
Check: the matching has three edges and covers \(2\cdot3=6\) vertices. This agrees with the vertex set \(\{1,2,3,4,5,6\}\), and the Tutte check included \(S=\varnothing\) as well as all nonempty deletion sets.
Worked Example: A Star Fails the Condition
Let \(G\) have vertex set \(\{x,a,b,c\}\) and edge set \(\{xa,xb,xc\}\). Choose \(S=\{x\}\). The remaining graph has vertex set \(\{a,b,c\}\) and no edges, so its three components are the singletons \(\{a\},\{b\},\{c\}\). Each has odd order \(1\), and therefore $$ o(G-S)=3>1=|S|. $$
This single violating set proves that \(G\) has no perfect matching. Directly, each of \(a,b,c\) would need to be paired with \(x\), since each has only that neighbor; a matching cannot use \(x\) in three edges. This direct check confirms the conclusion from the condition.
Worked Example: A Connected Graph with a Three-Component Obstruction
Let \(G\) have vertex set \(\{x,a,b,c,d,e\}\) and edge set \(\{xa,xb,xc,xd,xe,cd,de,ec\}\). The vertices \(c,d,e\) form a triangle, and \(x\) is adjacent to each of \(a,b,c,d,e\). Take \(S=\{x\}\). In \(G-S\), the vertices \(a\) and \(b\) are isolated, while \(c,d,e\) form one triangle component. These are three components, each of odd order: their orders are \(1,1,3\). Thus $$ o(G-S)=1+1+1=3>1=|S|. $$
By the proposition, \(G\) has no perfect matching. There is also a direct explanation: both \(a\) and \(b\) have only one neighbor, namely \(x\), so covering both would require two matching edges incident with \(x\). This is impossible in a matching. The triangle does not remove this obstruction: its vertices can be matched among themselves, but that cannot pair both \(a\) and \(b\).
Check: the graph has \(6\) vertices, and the violating set has size \(1\). After deletion, the component orders sum to \(1+1+3=5\), as required because \(6-1=5\) vertices remain. All three components are odd, giving the computed count \(3\).
Worked Example: Checking the Condition in a Complete Graph
Let \(G=K_6\), with vertex set \(\{1,2,3,4,5,6\}\) and edge set consisting of all \(15\) pairs of distinct vertices. For any \(S\subseteq V(G)\), put \(s=|S|\); then \(G-S\) is \(K_{6-s}\) when \(s<6\), and has no vertices when \(s=6\). A nonempty complete graph is connected, so \(o(G-S)=1\) if \(6-s\) is odd, and \(o(G-S)=0\) if \(6-s\) is even. For \(s=6\), the count is also \(0\).
When \(s=0\), \(6-s=6\) is even, giving \(o(G-S)=0\le0\). When \(s\ge1\), the count is either \(0\) or \(1\), and hence \(o(G-S)\le1\le s\). This covers every subset, so Tutte’s condition holds. The set \(\{12,34,56\}\) is a perfect matching: all three pairs are edges of \(K_6\), are disjoint, and cover the six vertices.
Check: the complete graph has \(\binom{6}{2}=6\cdot5/2=15\) edges, as specified. The proposed matching uses three of those edges and covers \(2\cdot3=6\) distinct vertices.
Reducing Repeated Checks by Symmetry
Proof. An automorphism is a bijection from \(V(G)\) to itself that preserves adjacency in both directions. If it maps \(S\) to \(T\), it also maps \(V(G)\setminus S\) bijectively to \(V(G)\setminus T\). Adjacency preservation means that it maps each component of \(G-S\) to a component of \(G-T\), with the same number of vertices. In particular, it preserves whether each component has odd order. Therefore the two graphs have the same number of odd components, and the bijection from \(S\) to \(T\) gives \(|S|=|T|\). \(\square\)
For example, the vertices of \(C_6\) can be rotated or reflected without changing adjacency. Consequently, deletion sets with the same arrangement up to a rotation or reflection have the same odd-component count. Symmetry can make a manual check shorter, but it does not change the quantifier: every possible set must still be covered, either directly or through a justified symmetry class. In the cycle example, the run-count argument handled all arrangements at once.
Common Pitfalls
Checking only one deletion set. For a graph that has a perfect matching, the condition must hold for every \(S\). Testing \(S=\varnothing\) alone checks only that the original graph has no odd components; it cannot rule out violations after other deletions.
Using equality as a failure. Tutte’s condition is \(o(G-S)\le |S|\), not \(o(G-S)<|S|\). Equality is allowed. For instance, in the star example, choosing \(S=\{x\}\) gives a strict violation \(3>1\). A computation giving \(o(G-S)=|S|\) would not itself disprove a perfect matching.
Counting odd vertices instead of odd components. The quantity \(o(G-S)\) counts components whose orders are odd; it does not count all vertices in those components. In the connected-graph example, the triangle contributes one odd component, not three, so the total is \(1+1+1=3\), not \(1+1+3=5\).
Check Your Understanding
For each question, identify the relevant deletion set and distinguish a verified condition from a single test.
- In the graph with vertex set \(\{1,2,3,4,5,6\}\) and edge set \(\{12,23,34,45,56,61\}\), take \(S=\{1,4\}\). List the components of \(G-S\), calculate \(o(G-S)\), and test the inequality.
- For the star with center \(x\) and leaves \(a,b,c\), calculate \(o(G-\{a\})\). Does this set violate Tutte’s condition?
- Let \(G=K_5\). For \(S=\varnothing\), calculate \(o(G-S)\). What does this test imply about a perfect matching?
- Explain why the triangle component in the connected-graph example contributes one to \(o(G-S)\), rather than three.
- Give the two checks needed to verify directly that a specified set of edges is a perfect matching.