Pair an optimal matching with a vertex cover

Try

A matching of size two proves that two simultaneous assignments are possible, but not that three are impossible. A vertex cover of size two supplies the missing upper bound: every edge meets the cover, so no matching can contain more than two disjoint edges. In bipartite graphs, Kőnig’s theorem guarantees that a maximum matching and a minimum cover have the same size. This produces a pair of independently checkable optimality certificates.

Predict

Predict why the cover bound works in every graph but equality may fail outside bipartite graphs. A triangle has maximum matching size one, while every cover needs two vertices. The weak inequality remains true because distinct matching edges require distinct covering vertices. The equality needs the alternating-reachability construction and its bipartite orientation.

Experiment

For a star with four leaves, compare several covers.

Candidate	Covers every edge?	Size
Center alone	Yes	1
All leaves	Yes	4
One leaf	No	1

Any one edge is a matching of size one. The center cover and that matching certify optimality; a large cover alone would give only a weak bound.

Understand

Let M be a maximum matching in a finite bipartite graph with parts L, R. Start alternating searches from every unmatched left vertex, using nonmatching edges left-to-right and matching edges right-to-left. Write Z_L, Z_R for the reached vertices. Define C=(L outside Z_L) union Z_R. To prove it covers every edge, suppose an edge goes from a reached left vertex to an unreached right vertex. If it is outside M, the search would traverse it. If it belongs to M, the reached left vertex is not an unmatched root and was reached from its matching partner, again a contradiction. Thus no edge is uncovered.

Apply

Every matched edge has either both endpoints reached or neither: traversal gives one direction, and a reached matched left vertex was reached through its partner. Therefore each matched edge contributes exactly one endpoint to C. Unmatched left vertices are roots and hence excluded from C. No unmatched right vertex is reached, since that would supply an augmenting path. Consequently size (C)=size (M). Combined with the universal matching-cover inequality, this proves Kőnig’s theorem. It also completes the earlier matching-based proof of Dilworth’s chain-partition theorem.

Continue

A maximum matching can be found by repeatedly searching for an augmenting path and flipping it. Berge’s criterion proves the stopping condition: the symmetric difference of a current matching with a larger one consists of alternating paths and cycles, and some path must have an excess edge from the larger matching. A straightforward search costs O(V+E) per augmentation, with at most min (size (L), size (R)) augmentations; more sophisticated layered methods improve this bound. State which algorithm is implemented rather than attaching the fastest known complexity to a simple search. Verify the final cover and matching directly, independently of the search history.

Return to the combinatorics and graph theory unit for prerequisite choices and targeted retries. Continue with explain the extra obstruction in general matching.