Explain the extra obstruction in general matching

Try

An even total number of vertices does not guarantee a perfect matching. The claw graph has one center and three leaves. Every matching can use only one edge because all edges meet the center. Removing that center leaves three odd components, revealing a bottleneck that Hall’s left-neighbor condition does not directly express in a general nonbipartite graph.

Predict

Predict why odd components require help from removed vertices. A matching pairs vertices two at a time. Inside an odd component at least one vertex cannot be paired internally, so a perfect matching must send an edge from that component to the removed set S. Distinct components require distinct vertices of S because matching edges cannot share an endpoint. This yields the necessary inequality odd (G−S)≤size (S).

Experiment

Compare several deletion tests.

Graph	Deleted set S	Odd components left	Obstruction?
Four-vertex claw	Center	3	Yes, 3>1
Four-cycle	One vertex	1	No, 1≤1
Two disjoint triangles	Empty	2	Yes, 2>0

A test that passes for one S says nothing about the other deletion sets. The theorem quantifies over every subset, including the empty set.

Understand

Tutte’s one-factor theorem states that a finite simple graph has a perfect matching if and only if odd (G−S)≤size (S) for every vertex subset S. Here odd means the number of connected components with an odd number of vertices, and a perfect matching covers each vertex exactly once. The empty graph has the empty perfect matching. The necessity proof is the parity argument above. We now prove sufficiency, including the local rearrangement needed to justify the maximal-graph step.

First build the matching in a structured graph

A vertex is universal when it is adjacent to every other vertex. Suppose U is a set of universal vertices and every component outside U is a clique, a graph containing every edge between its vertices. Let q count the odd cliques. If q≤size(U) and the total vertex count is even, match one vertex of each odd clique to a different vertex of U. Every clique then has an even number left, which can be paired internally. The unused vertices of U also number an even amount: the parity of the total equals the parity of size(U)+q. They form a clique, so pair them too.

For example, take three universal vertices and three disjoint triangles outside them. Match each universal vertex to one triangle vertex, then pair the other two vertices of each triangle. If instead only one universal vertex joins the three triangles, deleting it leaves three odd components but only one available helper. No perfect matching exists. The hypothesis “universal” matters: it guarantees the chosen cross-edges, not merely enough vertices on a list.

Saturate a proposed counterexample

Assume all Tutte inequalities hold but no perfect matching exists. The empty-set inequality says every component has even size, so the total vertex count is even. Add edges as long as doing so preserves the absence of a perfect matching. There are only finitely many possible edges, so this process stops at a graph H on the same vertices that is edge-maximal without a perfect matching. Maximal here means every missing edge would create one; it does not mean a maximum-size matching has been found.

For every fixed deletion set S, adding an edge either leaves components unchanged or merges two of them. Merging two odd components decreases their odd-component count by two; merging odd with even or even with even leaves that count unchanged. Edges meeting S do nothing after deletion. Thus the count never increases, and H still satisfies all Tutte inequalities. We will show H has the structured form just handled, giving a contradiction.

Why the remaining components must be cliques

Let U be all universal vertices of H. If a component of H−U is not a clique, take a shortest path between nonadjacent vertices in that component. Its first three vertices x, y, z satisfy xy and yz in H but xz absent; otherwise the path could be shortened. Since y is not universal, it has a nonneighbor w. The vertices x, y, z, w are distinct because x and z are neighbors of y.

Adding xz creates a perfect matching M1, which must use xz or H itself would already have one. Adding yw similarly creates M2 using yw. Every other edge of these matchings belongs to H. In their symmetric difference, each vertex has degree zero or two: common matching edges disappear, and every other vertex has one edge of each matching. Therefore its nontrivial components are even cycles with alternating M1 and M2 edges. Both artificial edges belong to these cycles because neither is in the other augmented graph.

If xz and yw lie on different cycles, replace the M1 edges on the xz cycle by its M2 edges. This removes xz and cannot introduce yw on another cycle. On all other vertices retain M1. Every vertex is still covered once, now entirely by H edges, a contradiction.

If the artificial edges lie on the same cycle, delete both. The cycle splits into two paths. Each has an even number of edges: along either segment the first and last retained edges belong to different matchings because the removed edges came from different matchings. Thus each path has an odd number of vertices. The endpoint y belongs to one path, together with exactly one of x and z; the other of x and z lies on the other path. Join y to that other endpoint using the existing edge xy or yz. On each path, remove the selected endpoint and pair the remaining consecutive vertices along the path. This uses only retained cycle edges, covers each path internally, and the connector covers the two removed endpoints. Retain M1 on all vertices outside this cycle. Again a perfect matching of H results.

Repair both possible cycle orders

This is a local hypothetical configuration in a contradiction proof. Its successful repair shows why it cannot occur in the proposed graph without a perfect matching. It is not an example of a graph violating Tutte’s theorem.

Order after x–z–a y, then ww, then y Connector to try x–yy–z Show edges First augmented matching M1Second augmented matching M2Your repair proposal

Solid edges belong to H; dashed x–z and y–w are artificial. Thick edges show: x–y, z–a, w–b, c–d.

After removing both artificial edges, the paths are z – a – y and w – b – c – d – x. Each has an even number of edges and an odd number of vertices.

Your connector joins different paths. Match consecutive remaining vertices on each path after removing the connector endpoints.

Perfect matching in H verified. Missing H edges: none. Unmatched vertices: none. Reused vertices: none.

Reset

Eight vertices and four local choices are checked exactly. This illustration does not replace the general cycle argument or implement a matching algorithm. Settings are temporary and do not award mastery.

Both possible cycle configurations contradict the assumed absence of a perfect matching. Hence every component of H−U is a clique. Apply H’s Tutte inequality at U: there are at most size(U) odd cliques. The total count is even, so the explicit structured construction gives a perfect matching of H, the final contradiction. Therefore the original G has a perfect matching. This proves the missing implication for all finite simple graphs, not only the illustrated size.

The proof uses saturation as a finite existence argument. It does not claim an efficient algorithm for deciding which edges can be added without creating a perfect matching. That decision already involves the matching problem. The alternating-cycle illustration checks local edge membership and vertex coverage; it is not an implementation of general blossom search.

For provenance, compare Diestel’s author-hosted Graph Theory, Chapter2, Theorem2.2.1. The proof here expands both symmetric-difference cycle cases and the endpoint repair; the visual cases are independently constructed teaching examples.

Apply

Augmenting paths remain the correct maximum-matching criterion in arbitrary graphs. The symmetric-difference proof of Berge’s lemma did not use bipartiteness. What changes is the search. In a bipartite graph, alternating reachability has a fixed left/right orientation. In a general graph, a nonmatching edge can join two outer (even-depth) vertices in the same alternating search tree. Together with their tree paths to the least common ancestor, which is the base, it forms an odd cycle called a blossom. Matching and nonmatching edges alternate around this cycle except for the two nonmatching edges incident to the base. Merely sharing a search parity is not a sufficient condition. Contracting such a structure and later expanding an augmenting path is the basis of Edmonds’ algorithm. A triangle attached to an alternating tree illustrates why marking a vertex visited once can lose useful route information. The extension below supplies the shrinking/lifting invariant, search logic and a bounded executable implementation.

Prove why shrinking an odd flower preserves augmentability

A blossom is more than an arbitrary odd cycle. Its base b is joined to an exposed search root r by an even-length alternating stem. Around the odd cycle, matching edges pair every vertex except b. The stem meets the cycle only at b. Contract the cycle to one vertex, remove its internal matching edges and retain the possible stem matching edge at b. Parallel edges keep their original endpoint labels for expansion; loops are discarded.

First toggle the stem. This changes no matching cardinality, moves the exposed vertex from r to b, and leaves the cycle’s internal matching pairs unchanged. By Berge’s criterion, two matchings of the same size in the same graph either both are maximum or both admit augmentation. The corresponding toggle in the contracted graph also preserves cardinality. We may therefore prove existence equivalence in the easier case with exposed base b.

Every edge from the blossom to its outside is now unmatched, because nonbase cycle vertices are matched internally and the base is exposed. If an augmenting path avoids the cycle, it survives contraction. If it meets the cycle, start from an exposed endpoint outside the cycle and stop at the first entry. Such an outside endpoint exists: b is the only exposed cycle vertex. The prefix alternates and its entry edge is unmatched. Contracting that entry produces an augmenting path ending at the exposed contracted vertex. There are no earlier repeated cycle visits because this is the first entry.

Conversely, a contracted augmenting path meeting the contracted vertex must end there, since that vertex is exposed. Let its incident original edge join outside vertex y to cycle vertex v. Of the two arcs from b to v around an odd cycle, exactly one has even length. That even arc alternates starting unmatched and ending matched (unless v=b, when it is empty). Attach it to the unmatched edge vy and the remaining path. Its internal vertices are in the blossom, while the rest of the path is outside, so this is a simple augmenting path in the original graph.

This proves augmentability equivalence after the stem toggle and hence before it. For an explicit path relative to the untoggled matching, take the new larger matching obtained above, form its symmetric difference with the original matching, and select a component with one more new edge. The symmetric difference decomposes into alternating paths/cycles, so such a component exists and is an original augmenting path. This also avoids the incorrect assertion that any expanded alternating walk is automatically a simple path.

The search invariant and its stopping case

Start alternating trees at exposed vertices. Outer vertices have even tree depth; inner vertices have odd depth. From an outer vertex, an edge to an unreached matched vertex adds that vertex as inner and its mate as outer. An edge joining outer vertices of different trees gives an augmenting path through their roots. An edge joining distinct outer vertices of one tree gives the odd cycle formed by the two paths to their lowest common ancestor and the new edge. Shrink that flower and continue. An edge internal to a contracted blossom is ignored; an edge to an already inner vertex does not alone reveal an augmenting path.

If every outer adjacency is exhausted, no augmenting path exists in the contracted graph: the first edge of a hypothetical path that exits the reached forest would have triggered a growth or augmentation; if it never exits, its exposed opposite endpoint and alternating parity force an outer-to-outer connection already processed. Expand contractions using the proved equivalence. Berge then certifies maximum cardinality. A visited-once ordinary breadth-first search lacks this invariant and can miss paths through odd cycles.

A straightforward implementation needs at most O(n) augmentations. A search scans O(m) adjacency entries and can do O(n) work for each blossom bookkeeping event, giving a conservative O(nm+n²) bound per search and a polynomial overall bound. Dense-array implementations can obtain O(n³) overall by more careful accounting; the bound is not inferred from the small examples below. Nested blossoms must retain bases and parent/edge representatives; forgetting this data invalidates lifting.

Remove an edge, predict the matching, then inspect

The bounded CPU solver runs Edmonds' alternating-forest algorithm. The endpoint checker separately verifies that its reported edges form a matching; that checker alone does not prove maximum size. Controls and counts are temporary and do not award mastery.

Graph Triangle with a tailTwo odd cycles joined by a bridgeClaw obstructionFive-cycle with a tail

Vertices: 0, 1, 2, 3. Before removing an edge, write your predicted maximum and whether an odd cycle remains.

Edge 0–1: presentEdge 1–2: presentEdge 2–0: presentEdge 2–3: present

Maximum matching size: 2. Edges: 0–1, 2–3. Exposed vertices: none.

Endpoint/edge validity: passes. Search contractions: 1; directed adjacency scans: 4; augmentations: 2.

Interpret the changed case

Removing the bridge between two triangles leaves two odd components, each with one exposed vertex; size falls from 3 to 2. In the claw, deleting the center leaves three odd components, so Tutte's condition fails. A different maximum matching may be equally valid. Contraction counts depend on deterministic vertex/neighbor order and are not an invariant of the graph.

Restore this graph

Changed path exercise

Take the cycle 0–1–2–3–4–0 with matching edges 1–2 and 3–4, exposed base 0, and a new exposed vertex 5 joined only to 3. A contracted augmenting edge must expand through the even arc 0–4–3, then 3–5. Toggling yields matching edges 0–4,3–5 and the unchanged 1–2, of size 3. The other arc 0–1–2–3 has odd length and would put two consecutive unmatched edges at 3 when followed by 3–5. State the parity before toggling, then check every endpoint independently.

The CMU15-850 matching notes, chapter 7, inspected 30 October 2026, give a primary teaching reference for shrinking and lifting. The local bounded implementation keeps search bases/parents, has an independent edge-validity checker, and is compared against a separate subset-recurrence oracle in tests. Those finite tests support the implementation; the proof above, not test enumeration, establishes the general contraction argument.

Continue

Use two different certificates appropriately. A perfect matching is a short positive certificate checked by endpoint coverage. A subset S with too many odd components is a negative certificate checked by deleting S, finding components and counting their parity. If neither certificate is found by a limited search, report the result as unresolved rather than declaring feasibility. This lesson proves the general obstruction and its converse. The added blossom section separates the general proof from bounded execution and its independently checked outputs.

Return to the combinatorics and graph theory unit for prerequisite choices and targeted retries. Continue with color graphs with structural orderings.