Why Odd Components Require Vertices in the Deleted Set
A perfect matching pairs every vertex with exactly one other vertex. If a set \(S\) of vertices is deleted, the remaining graph may break into components. An odd component cannot have all its vertices paired among themselves: internal matching edges cover vertices two at a time. Its unpaired vertex or vertices must therefore be matched to vertices of \(S\). The key point is that different odd components need different vertices of \(S\).
Throughout, graphs 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 exactly one matching edge. For \(S\subseteq V(G)\), \(G-S\) is the induced subgraph on \(V(G)\setminus S\). A component is a maximal connected subgraph, and an odd component is a component with an odd number of vertices. Write \(o(G-S)\) for the number of odd components of \(G-S\); in particular, \(o(G-S)=0\) if \(G-S\) has no vertices.
This is a necessary condition: it must hold whenever a perfect matching exists. The inequality alone is not asserted here to produce a perfect matching; proving the converse is the content of Tutte’s theorem.
Proof by Assigning Matching Partners
Proof. Let \(M\) be a perfect matching of \(G\), and fix any \(S\subseteq V(G)\). Consider an odd component \(C\) of \(G-S\). A matching edge incident with a vertex of \(C\) either has both endpoints in \(C\), or has its other endpoint outside \(C\). In the latter case, that other endpoint must be in \(S\): an edge from \(C\) to a different component of \(G-S\) would join those components, contradicting that they are distinct components.
Suppose no edge of \(M\) joins \(C\) to \(S\). Since \(M\) is perfect, every vertex of \(C\) must then be matched to another vertex of \(C\). Those matching edges would partition \(V(C)\) into pairs, so \(|V(C)|\) would be even. This contradicts that \(C\) is odd. Thus at least one edge of \(M\) joins \(C\) to \(S\).
Choose one such edge for each odd component of \(G-S\). These chosen edges have distinct endpoints in \(S\). Indeed, if two chosen edges shared an endpoint in \(S\), they would share a vertex, which is forbidden because \(M\) is a matching. Therefore the number of odd components is at most the number of vertices in \(S\), giving \(o(G-S)\le |S|\). This reasoning also covers \(S=\varnothing\): then no odd component can exist. If \(G-S\) is empty, there are no odd components and the inequality reads \(0\le |S|\). \(\square\)
The proof gives a precise accounting rule. Each odd component uses at least one matching edge that leaves it, and the endpoint of that edge outside the component lies in \(S\). A vertex of \(S\) cannot serve two such components, because a perfect matching uses each vertex exactly once.
Its vertices cannot all be paired by matching edges whose two endpoints stay inside that component.
Because the matching is perfect, some vertex of the component is matched outside it. The outside endpoint must be in \(S\).
Different components use different matching edges and therefore different vertices of \(S\). Hence their number is at most \(|S|\).
A Parity Check for the Count
Proof. The components of \(G-S\) partition its vertex set, which has \(|V(G)|-|S|\) vertices. Each even component contributes an even number to this total. Each odd component contributes an odd number, which is congruent to \(1\) modulo \(2\). Adding the component sizes therefore gives a total with the same parity as the number of odd components. Thus \(o(G-S)\) and \(|V(G)|-|S|\) have the same parity. If \(G-S\) is empty, both numbers are zero, so the statement still holds. \(\square\)
When \(G\) has a perfect matching, its vertices are partitioned into pairs, so \(|V(G)|\) is even. The proposition then implies that \(o(G-S)\) has the same parity as \(|S|\). This parity fact is a useful check on a component count, but it does not replace the inequality: a number can have the right parity and still be larger than \(|S|\).
Worked Example: A Tight Bound on a Path
Let \(G\) have vertex set \(V(G)=\{1,2,3,4,5,6\}\) and edge set \(E(G)=\{12,23,34,45,56\}\). The edges \(12,34,56\) form a perfect matching: they share no endpoints and cover all six vertices. Take \(S=\{2,5\}\), so \(|S|=2\).
Deleting \(S\) leaves vertices \(\{1,3,4,6\}\). Of the original edges, only \(34\) has both endpoints left. Thus the components of \(G-S\) are the singleton \(\{1\}\), the two-vertex component \(\{3,4\}\), and the singleton \(\{6\}\). Their orders are \(1,2,1\), respectively, so exactly two components are odd:
The matching shows the assignments in the proof: vertex \(1\) is matched to \(2\in S\), and vertex \(6\) is matched to \(5\in S\). These are distinct vertices of \(S\). The component \(\{3,4\}\) is even and is matched internally by edge \(34\).
Check: the remaining graph has \(1+2+1=4\) vertices, as \(|V(G)|-|S|=6-2=4\). Its two odd components give \(o(G-S)=2\), which has the same parity as \(4\) and meets the bound \(2\le 2\).
Worked Example: A Perfect Matching with Strict Inequality
Let \(G\) have vertex set \(V(G)=\{1,2,3,4\}\) and edge set \(E(G)=\{12,23,34,41\}\), a 4-cycle. The edges \(12\) and \(34\) form a perfect matching. Set \(S=\{1,2\}\), so \(|S|=2\).
After deleting \(1\) and \(2\), the remaining vertices are \(\{3,4\}\), and edge \(34\) remains. Therefore \(G-S\) has one component of order \(2\), which is even. It follows that \(o(G-S)=0\), and the inequality is strict:
Here the matching edge \(12\) lies entirely inside \(S\). The theorem does not require every vertex of \(S\) to be assigned to an odd component; it only says that distinct odd components need distinct vertices of \(S\). In this example there are no odd components to assign.
Check: \(G-S\) has \(4-2=2\) vertices, both in the even component \(\{3,4\}\). Thus \(o(G-S)=0\), consistent both with \(0\le2\) and with the parity proposition, since \(0\) and \(2\) are both even.
Worked Example: A Set That Rules Out a Perfect Matching
Let \(G\) have vertex set \(V(G)=\{0,1,2,3\}\) and edge set \(E(G)=\{01,02,03\}\), the star with center \(0\). Choose \(S=\{0\}\), so \(|S|=1\).
Deleting \(0\) leaves three isolated vertices, \(\{1\}\), \(\{2\}\), and \(\{3\}\). Each is an odd component, so
The necessary condition fails, so \(G\) cannot have a perfect matching. Directly, every edge uses the center \(0\), and a matching can contain at most one of the three edges. Such a matching can cover at most two of the four vertices, not all four.
Check: the three remaining components have total order \(1+1+1=3=|V(G)|-|S|\), and their odd-component count is \(3\). Both \(3\) and \(|S|=1\) are odd, as the parity proposition predicts; the obstruction is the inequality \(3\le1\), which is false.
Common Pitfall: Counting All Components
In the path example, \(G-S\) has three components, but only two are odd. A mistaken calculation might count all components and write \(3>|S|=2\), then conclude that the graph violates the necessary condition. That conclusion is wrong: the condition counts odd components, not components of every order. The component \(\{3,4\}\) has two vertices and can be matched internally, so it does not need a vertex of \(S\).
The reverse mistake is also possible: checking just one set \(S\) that satisfies the inequality does not prove that a graph has a perfect matching. The theorem says that a perfect matching forces the inequality for every \(S\). A violation for even one set rules out a perfect matching, as in the star example; satisfying the inequality for a particular set gives only that particular necessary check.
This condition is useful because it turns a matching question into a structural count. Removing a small set \(S\) cannot create more odd components than there are available matching partners in \(S\). The argument depends on both ingredients: odd components cannot be matched entirely internally, and matching edges cannot reuse a vertex of \(S\).
Check Your Understanding
For each question, distinguish the odd components from all components and state the set \(S\) being considered.
- In the path example, why can the component \(\{3,4\}\) be matched without using a vertex of \(S\)?
- Suppose \(G\) has a perfect matching and \(G-S\) has four odd components. What lower bound does the theorem give for \(|S|\)?
- Explain why an edge from a component of \(G-S\) to a vertex outside that component must end in \(S\).
- For the star on \(\{0,1,2,3\}\), compute \(o(G-\{0\})\) and explain why the inequality rules out a perfect matching.
- Why does the parity proposition alone not prove the necessary inequality?