Motivation
In a bipartite graph, Hall's condition compares a chosen set with its neighbors on the other side. A general graph has no fixed pair of sides, and odd cycles make that language inadequate. An odd component cannot match all of its vertices internally. To avoid leaving one vertex unmatched, it must use an edge to a deleted boundary set.
That observation produces a necessary condition for a perfect matching. Its sufficiency is much less immediate: perhaps many different odd-component obstructions interact. We prove that no other obstruction exists, using an edge-maximal graph without a perfect matching. Two hypothetical extra edges and an alternating-cycle argument force the remaining components to have a very rigid form.
This section develops matching in general graphs beyond the earlier bipartite theorem. The proof is an existence argument; the complete polynomial blossom-search algorithm and weighted nonbipartite matching are outside its scope.
Definitions
Definition 6.2.1
(Perfect matchings and odd-component obstruction)
Let be a finite simple undirected graph. A matching is a set of edges with no shared endpoints. It is perfect if every vertex belongs to one selected edge. The empty graph has the empty perfect matching. Write for the largest matching size and for the number of odd-order connected components after deleting a vertex set .
The deficiency expression is , and define
The maximum is over finitely many sets. It is nonnegative because the empty set gives a nonnegative value. All its candidate values have the same parity as .
A universal vertex is adjacent to every other vertex. A graph is saturated without a perfect matching when it has no perfect matching, but adding any missing edge creates one. Such a graph can be obtained from any graph without a perfect matching by adding edges as long as no perfect matching is created; finiteness ensures that this existence construction stops.
Theorem/Proposition
Theorem 6.2.2
(Odd-component criterion for a perfect matching)
A finite graph has a perfect matching if and only if
The condition includes the empty set and all original vertices. In particular it forces even order, rather than assuming even order silently.
Theorem 6.2.3
(Exact matching deficiency)
For every finite graph on vertices,
Thus the maximum excess of odd components over deleted vertices is exactly the smallest number of vertices left unmatched, not merely a lower bound. A graph of odd order has a matching missing exactly one vertex if and only if for every .
Theorem 6.2.4
(Structure of a saturated obstruction)
In a saturated graph without a perfect matching, let be the set of universal vertices. Every connected component of is a complete graph. If such a graph also satisfied the odd-component condition, its universal vertices could match the odd components and pair among themselves, producing a contradiction.
Proof sketch or proof idea
Proof
(Necessity, the lower bound and parity)
For necessity, take any perfect matching and any deleted set . In each odd component of , not all vertices can be matched to one another. At least one matching edge must leave that component. Its other endpoint belongs to , since distinct components have no edges between them. Different odd components use different vertices of , because a matching does not reuse endpoints. Hence their number is at most .
More generally, in any matching at most odd components can send a selected edge to . Every remaining odd component leaves at least one vertex unmatched. Therefore every matching leaves at least vertices unmatched. Maximizing gives the lower bound .
The parity statement follows because the sum of component orders is . Modulo two it equals the number of odd components. Consequently has the same parity as , for every .
The alternating-cycle structural lemma
Proof
(Saturated graphs: universal vertices and cliques)
Suppose a saturated graph has vertices with edges , but no edge . We claim that must be universal. If not, choose a vertex not adjacent to . The four vertices are distinct, since are adjacent to .
Adding creates a perfect matching , and it must use that added edge. Adding creates a perfect matching , which must likewise use its added edge. Regard their union as a multigraph, retaining two labeled copies of a shared edge. Every vertex has one edge from each matching, so the union decomposes into even cycles whose edges alternate between the two matchings. A doubled common edge is a two-edge cycle.
If the two added edges are in different alternating cycles, switch from to on the cycle containing . This removes without introducing . The unchanged edges of and the switched edges are all in the original graph, giving a forbidden perfect matching.
Therefore both added edges lie in the same alternating cycle. Remove those two edges. Since they belong to opposite matchings, the cycle splits into two paths, each having an odd number of vertices. Each path has one endpoint from and one from . In particular is an endpoint of one path, and exactly one of is an endpoint of the other.
Join those two endpoints by the original edge or , as appropriate. Deleting the joined endpoint from each of the two odd paths leaves an even number of vertices on each path, which can be matched in consecutive pairs along its original edges. Together with the joining edge and matching edges on the other cycles, this again forms a perfect matching entirely in the original graph. This contradiction proves the claim.
Now let consist of all universal vertices. If a component of were not complete, a shortest path between two nonadjacent vertices in that component would begin with two edges whose endpoints are not adjacent. Its middle vertex is outside , contradicting the claim. Thus every such component is complete.
Proof X-ray
Two forbidden extra edges force a usable original edge
Saturation turns each missing edge into a hypothetical perfect matching. Their alternating union isolates the only edges unavailable in the original graph. If they lie on different cycles, a switch avoids both. If they lie on one cycle, removing them leaves two odd paths, and the known two-edge configuration supplies a cross-edge that joins their exposed endpoints. The structural conclusion comes from covering both cases.
Sufficiency of the odd-component condition
Proof
(Matching the odd cliques into the universal set)
Assume the condition holds but there is no perfect matching. Add edges until the graph is saturated without one. The condition is preserved by adding edges: after any fixed deletion , a new edge either stays inside a component or merges two components. Merging two odd components reduces the odd-component count by two; merging any other pair does not increase it.
Apply the structural lemma to this enlarged graph. Its nonuniversal components are cliques. Let of them have odd order. The condition at the universal set says . Match one vertex in each odd clique to a different vertex of , using universality. Pair all remaining vertices within each clique; even cliques pair internally without using .
The graph has even order because the condition at the empty set forbids any odd components. The parity of the total order is also the parity of , since only the odd cliques contribute. Therefore is even. The still unused universal vertices form a clique of that even size and can be paired with one another. We have built a perfect matching, contradicting saturation without one. This proves sufficiency and the criterion.
Converting the obstruction into exact deficiency
Proof
(Adjoining universal vertices)
Put and add new vertices, joining them to one another and to every original vertex. Call the enlarged graph . Its order is even by the proved parity statement. We verify its odd-component condition for every deletion .
If at least one new vertex survives, all surviving vertices are in one component. For nonempty , its odd-component count is at most one and hence at most . For empty , the total order is even, so the count is zero. If no new vertex survives, write as all new vertices together with original vertices . The remaining graph is , and the definition of gives .
The criterion supplies a perfect matching of . Delete its new vertices and their incident selected edges. At most original vertices lose partners, so a matching in leaves at most vertices unmatched. Combined with the earlier lower bound this proves equality. When the same argument simply applies the criterion directly to .
For odd order, every candidate deficiency is odd and nonnegative at its maximum, so . The stated near-perfect condition says , and hence is equivalent to , finishing that corollary.
What the existence proof does not compute efficiently
The saturation argument asks whether each prospective extra edge creates a perfect matching; it has not supplied an efficient way to answer that question. Likewise, enumerating every deletion set gives a finite but exponential test. The equality is a structural certificate theorem, not a polynomial matching implementation hidden inside an existence construction.
The earlier bipartite augmenting-path argument avoids some of this difficulty because its alternating search has a fixed side structure. In general graphs odd alternating structures require additional handling. The theorem here explains the exact obstruction independently of such an implementation, and it gives a way to verify a supplied lower certificate: delete its displayed vertices and count the odd components.
Worked examples
Worked example 6.2.5
(Three odd branches obstruct a perfect matching at even order)
Take three disjoint triangles and one extra hub vertex. Join the hub to one chosen vertex of each triangle, with no other cross edges. There are ten vertices. Deleting the hub leaves three odd components, so the condition fails because three exceeds one.
A matching of size four exists: match the hub into one triangle, pair the other two vertices of that triangle, and use one edge within each other triangle. It leaves two vertices unmatched. The hub deletion supplies deficiency two, and the displayed matching shows that no stronger lower bound can occur. Thus the maximum matching size is exactly four, although every vertex has degree at least two.
Worked example 6.2.6
(An odd cycle has exactly one unmatched vertex)
On the cycle with vertices in cyclic order, select and , leaving one vertex unmatched. The empty deletion set gives one odd component and therefore deficiency at least one. The matching lower-bound argument also shows every deficiency expression is at most the one unmatched vertex of this matching.
Hence and the matching is maximum. Odd order prevents perfection, but does not force three or more unmatched vertices. The exact deficiency theorem captures that distinction.
Worked example 6.2.7
(A complete even graph satisfies every deletion test)
In , deleting leaves a clique of order . It has one odd component when that order is positive and odd, and zero otherwise. If is empty the count is zero; if it is nonempty the count is at most one and thus at most .
The condition holds, and two disjoint edges give a perfect matching. The graph contains triangles, so nonbipartiteness itself is no obstruction. The relevant condition concerns odd components after deletion, not the absence of odd cycles in the original graph.
Concept lensCombinatorial
Each odd component demands a distinct boundary partner or an unmatched vertex
An odd component has a parity deficit of one if all its matching edges stay inside. A deleted vertex can absorb at most one such deficit. Maximizing the excess over all boundaries finds the exact number of unavoidable unmatched vertices. The sufficiency proof shows that no additional hidden deficit remains once all these parity demands are satisfied.
Common mistakes
Counterexample mode
Even total order does not cancel separated odd demands
The star with three leaves has four vertices, but deleting its center leaves three odd singleton components and only one deleted vertex to serve them. Its maximum matching has one edge and leaves two vertices unmatched. Even order alone cannot replace the odd-component condition.
Common mistake
(Odd cycles are not odd components)
Do not count odd cycles instead of odd connected components. An even clique contains many odd cycles and still has a perfect matching; passes every deletion test.
Common mistake
(High degree or connectivity does not prevent a deficient deletion)
Do not assume a high minimum degree or a connected original graph prevents a small deletion from exposing several independent odd demands. The three triangles joined to a hub form a connected graph of minimum degree two, yet deleting the hub alone leaves three odd components and forces two unmatched vertices.
Summary
Odd components give necessary parity demands on any matching. A saturated-obstruction argument proves that satisfying every such demand is sufficient for a perfect matching. Adding universal vertices then converts the criterion into the exact unmatched-vertex formula. These structural proofs provide complete certificates while leaving the efficient general matching search as a separate algorithmic task.
Exercises
Quick check
(Find the maximum matching and exact deficiency of the disjoint union of two triangles.)
Use the empty deletion set and a displayed matching to bound the same quantity from both sides.
Solution · Answer
The empty set exposes two odd components, so every matching leaves at least two vertices unmatched. Selecting one edge in each triangle gives two edges and leaves exactly two unmatched. Thus and . Connecting the components conceptually in a drawing would change the graph; their separate odd demands cannot share a matching edge that is not present.
Quick check
(For the star with four leaves, find a deletion set achieving maximum deficiency and explain how three added universal vertices permit a perfect matching of the enlarged graph.)
Pair the center to one leaf before assigning the other leaves.
Solution
Deleting the center leaves four odd singleton components, giving excess . A single center-to-leaf edge is a maximum matching, since all edges share the center, and it leaves three vertices unmatched. Thus the maximum deficiency is exactly three.
Add three universal vertices. Match the center to one original leaf and match each new vertex to a different remaining leaf. These four edges cover all eight vertices. Removing the new vertices leaves precisely the original one-edge matching, illustrating the deficiency proof without requiring any new-new selected edge.
Quick check
(Prove directly from the perfect-matching criterion that an odd-order graph has a matching missing one vertex exactly when adjoining one universal vertex gives a perfect matching.)
Inspect the partner of the new vertex and verify the criterion using the original near-perfect inequalities.
Solution
A matching missing one vertex extends to a perfect matching by pairing that vertex to the new universal vertex. Conversely, delete the new vertex from a perfect matching; its one original partner becomes unmatched and all other original vertices remain matched.
For the criterion, suppose for every original . In the enlarged graph, a deletion including the new vertex leaves and has size , so satisfies the condition. If the new vertex survives, the remaining graph is connected; a nonempty deletion leaves at most one odd component, and an empty deletion leaves even total order. Thus every deletion satisfies the criterion, yielding the claimed perfect matching and the original near-perfect matching.