Why a Tight Set Gives a Reduction
A tight set identifies a precise balance: deleting its vertices leaves as many odd components as the number of deleted vertices. In a perfect matching, each odd component must use at least one matching edge to a vertex outside that component. When the number of odd components equals the number of deleted vertices, this balance suggests pairing each odd component with a different vertex of the deleted set. The pairing is a useful reduction, but it has two distinct parts: first find the component-to-vertex assignment; then ensure the chosen attachment edges leave matchable graphs inside the components.
All graphs in this tutorial are finite and simple. A matching is a set of edges with no shared endpoints, and it is perfect if every vertex is incident with one of its edges. A component is odd or even according as its number of vertices is odd or even. Write \(o(H)\) for the number of odd components of a graph \(H\). For \(S\subseteq V(G)\), \(G-S\) is the subgraph induced by the vertices outside \(S\).
For the assignment step, form a bipartite graph whose left vertices are the odd components of \(G-S\), whose right vertices are the vertices of \(S\), and where a component is adjacent to \(s\in S\) exactly when an edge of \(G\) joins \(s\) to a vertex of that component. Hall’s theorem says that this bipartite graph has a matching covering its left side if and only if every collection \(X\) of left vertices has at least \(|X|\) neighbors on the right. Hall’s theorem is used here in its standard form from the earlier material on Hall’s Marriage Theorem.
The Component Assignment
Proof. Let \(X\) be any collection of odd components of \(G-S\), and let \(N_S(X)\) be the set of vertices of \(S\) adjacent to at least one component in \(X\). Delete \(N_S(X)\) from \(G\). Each component in \(X\) remains a component of \(G-N_S(X)\): there are no edges from it to another component of \(G-S\), and by the definition of \(N_S(X)\) it has no edge to any vertex of \(S\setminus N_S(X)\). Each of these \(|X|\) components is odd. Therefore \(o(G-N_S(X))\ge |X|\). The Tutte condition applied to \(N_S(X)\) gives \(o(G-N_S(X))\le |N_S(X)|\), so \(|N_S(X)|\ge |X|\). Hall’s theorem now gives a matching covering all odd components. Tightness gives \(r=o(G-S)=|S|\); thus a matching of all \(r\) components to distinct vertices of \(S\) uses every vertex of \(S\). \(\square\)
This lemma supplies an assignment, not yet a perfect matching of \(G\). For each assigned pair \((C_i,s_i)\), an edge from \(s_i\) to some vertex \(v_i\in C_i\) is available by the definition of adjacency. To finish the reduction, the remainder \(C_i-v_i\) must have a perfect matching. Every even component of \(G-S\) must also have a perfect matching. These are local requirements: the assignment lemma alone does not prove them.
Proof. Take the assignment edges \(s_iv_i\), a perfect matching of each \(C_i-v_i\), and a perfect matching of each even component of \(G-S\). The chosen assignment edges have distinct endpoints in \(S\), because the assigned vertices \(s_i\) are distinct; they also have distinct endpoints in \(G-S\), because the components \(C_i\) are disjoint. Each matching inside a component avoids its assigned vertex \(v_i\), and different components have disjoint vertex sets. The union of all these edges is therefore a matching. It covers every \(s_i\), every vertex of every odd component, and every vertex of every even component. The assignment uses all of \(S\), so it covers every vertex of \(G\). Hence the union is a perfect matching. \(\square\)
The components and the graphs \(C_i-v_i\) have fewer vertices than \(G\) whenever \(S\) is nonempty and \(G-S\) is nonempty. This is why the reduction is suited to inductive arguments: a large matching problem is replaced by matching problems on smaller pieces. But the existence of a smaller matching in each piece must be established under the hypotheses of the argument; it cannot be inferred from the equality \(o(G-S)=|S|\) alone.
Worked Reductions
Worked Example: Pairing Odd Components and Combining Matchings
Let \(V(G)=\{x,y,a,b,c,d,e,f\}\) and \(E(G)=\{ab,bc,ca,xa,ya,yd,ef\}\). Take \(S=\{x,y\}\). The components of \(G-S\) are the triangle on \(\{a,b,c\}\), the singleton \(\{d\}\), and the edge on \(\{e,f\}\). The first two are odd, so \(o(G-S)=2=|S|\).
The odd-component neighborhoods in \(S\) are \(N_S(\{a,b,c\})=\{x,y\}\) and \(N_S(\{d\})=\{y\}\). For the first component alone, the neighborhood has size \(2\ge1\); for the second alone, it has size \(1\ge1\); for both, the neighborhood has size \(2=2\). Thus the assignment can pair the triangle with \(x\) and \(\{d\}\) with \(y\). Use the edges \(xa\) and \(yd\). Removing the assigned endpoints \(a\) and \(d\) leaves the edge \(bc\) and the edge \(ef\), each of which is itself a perfect matching of its component.
The resulting matching is \(\{xa,yd,bc,ef\}\). Its edges have disjoint endpoints, and together they cover all eight vertices. As an independent check, the four edges contribute \(4\cdot2=8\) distinct endpoints, equal to \(|V(G)|=8\). The graph is explicitly partitioned into the four matched pairs \(\{x,a\},\{y,d\},\{b,c\},\{e,f\}\).
Worked Example: Tightness Alone Does Not Ensure a Perfect Matching
Let \(V(G)=\{s,a,b,c\}\) and \(E(G)=\{ab,bc,ca\}\). Thus \(s\) is isolated and \(a,b,c\) form a triangle. Set \(S=\{s\}\). Then \(G-S\) is the triangle, so \(o(G-S)=1=|S|\): \(S\) is tight.
Nevertheless, \(G\) has no perfect matching, because no edge is incident with \(s\). In fact, \(G\) fails the Tutte condition already for \(X=\varnothing\): \(G\) has two odd components, the isolated vertex and the triangle, so \(o(G)=2>0=|X|\). This example shows why the assignment lemma assumes the Tutte condition in addition to tightness. It also shows why a component assignment must use actual edges from \(S\) to the odd components.
Worked Example: The Attachment Endpoint Matters
Let \(V(G)=\{s,a,b,c,d,e\}\) and \(E(G)=\{ab,bc,cd,de,sa,sb\}\). With \(S=\{s\}\), the graph \(G-S\) is the path \(a-b-c-d-e\), which is one odd component. Thus \(o(G-S)=1=|S|\). The component is adjacent to \(s\) at both \(a\) and \(b\), so either attachment is available in the component-assignment graph.
If we attach \(s\) to \(a\), deleting \(a\) from the component leaves the path \(b-c-d-e\). Its matching \(\{bc,de\}\) is perfect. Together with \(sa\), this gives the perfect matching \(\{sa,bc,de\}\) of \(G\); its three edges cover the six vertices exactly once.
By contrast, choosing the other available edge \(sb\) leaves \(G-S\) with \(b\) deleted. The remaining vertices are \(a,c,d,e\), with \(a\) isolated and \(c-d-e\) a path on three vertices. A perfect matching cannot cover the isolated vertex \(a\). Thus an available edge from a component to \(S\) is not, by itself, enough: the selected endpoint must also leave a perfectly matchable remainder.
For a check on the original graph, the displayed matching \(\{sa,bc,de\}\) covers \(s,a,b,c,d,e\), so a perfect matching does exist. The failure was only in the particular attachment choice \(sb\), not in the graph or the component assignment.
What the Reduction Does—and Does Not—Claim
The main structural gain is that the odd components can be paired injectively with vertices of \(S\), and tightness makes this pairing a bijection. Each such pair is intended to contribute one crossing edge to the final matching. Once that edge is chosen, the remaining vertices of its odd component form a smaller matching problem. Even components contribute their internal matching without using a vertex of \(S\).
The Tutte condition is essential for the Hall step: it bounds the number of odd components that remain after deleting the neighbors of any selected collection of odd components. Tightness is essential for the final count: it says the two sides of the assignment have equal size. Neither statement by itself supplies the internal matchings. The reduction is complete only when the local component matchings and attachment endpoints have been justified as well.
Common mistake. A frequent error is to reason, “There are \(|S|\) odd components and \(|S|\) vertices in \(S\), so pair them arbitrarily.” Equal cardinalities do not imply that the required edges exist. Hall’s condition proves that a pairing using actual adjacencies exists when the Tutte condition holds. A second error is to choose any available attachment edge and assume the component remainder has a perfect matching; the path example shows that this can fail. Check both the adjacency assignment and the matching left after each chosen endpoint is removed.
Check Your Understanding
For each question, distinguish the Hall assignment from the additional component-matching requirements.
- In the component-assignment lemma, why does every component in a selected collection \(X\) remain an odd component after deleting \(N_S(X)\)?
- Why does tightness turn a matching covering all odd components into a bijection with \(S\)?
- Give the precise local condition needed in an odd component \(C_i\) after choosing an attachment edge \(s_iv_i\).
- For the path example on \(\{a,b,c,d,e\}\), explain why deleting \(a\) leaves a perfect matching but deleting \(b\) does not.
- Which hypothesis fails in the graph consisting of an isolated vertex \(s\) and a triangle when \(S=\{s\}\)?