Skip to content
Tutorials Center
My learning

Topics

Lesson 23 of 36 · Coloring and Matching

Hall's Theorem, König's Theorem and Stable Matching

When does a perfect matching exist? Learn Hall's condition, König's min vertex cover theorem, and the Gale-Shapley stable matching algorithm with runnable Python examples.

An algorithm that finds a maximum matching is useful, but it only tells you the answer. Theorems tell you why. In this lesson you will learn three results that explain bipartite matchings: Hall's theorem says exactly when every vertex on one side can be matched, König's theorem ties matchings to vertex covers, and the Gale-Shapley algorithm solves a different but related problem in which both sides have preferences.

Hall's marriage theorem

Let G be a bipartite graph with sides L and R. For a set S ⊆ L, write N(S) for the set of its neighbors in R. If some set S of workers together knows fewer jobs than there are workers (|N(S)| < |S|), no matching can cover all of S: there are too few jobs among them. Surprisingly, this obvious obstruction is the only one.

Hall's theorem. A bipartite graph has a matching that covers every vertex of L if and only if |N(S)| ≥ |S| for every subset S ⊆ L.

The condition is called Hall's condition. A set that violates it is a Hall violator (a "witness" that no complete matching exists). A corollary: a k-regular bipartite graph (k ≥ 1) always has a perfect matching, because any set S sends out k|S| edges that land on N(S), and each vertex of N(S) receives at most k, so |N(S)| ≥ |S|. Applying that repeatedly proves König's edge-coloring theorem from the previous lesson: peel off one perfect matching at a time.

Python Check Hall's condition and find a violator

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Checking all subsets costs 2^|L|, which is fine for a classroom example but useless in practice. In real code run a matching algorithm such as Hopcroft-Karp: if it cannot match a left vertex, the set of left vertices reachable from that vertex by alternating paths is a Hall violator.

König's theorem: matching equals vertex cover

A vertex cover is a set of vertices that touches every edge. In any graph, a vertex cover must contain at least one endpoint of each matching edge, and those endpoints are all distinct, so (size of any vertex cover) ≥ (size of any matching). In bipartite graphs the two optimums are equal:

König's theorem. In a bipartite graph, the size of a maximum matching equals the size of a minimum vertex cover.

The proof is constructive and gives an algorithm. Take a maximum matching M. Let Z be the set of vertices reachable from free left vertices along alternating paths (non-matching edges from left to right, matching edges from right to left). Then the minimum vertex cover is (L \ Z) ∪ (R ∩ Z).

Two related equalities follow by complementing: the maximum independent set has size |V| − (min vertex cover), and the minimum edge cover has size |V| − (max matching) (Gallai).

Python Minimum vertex cover from a maximum matching

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Each marked cell is an edge between its row vertex and its column vertex. Covering the cell means choosing its row or its column, so the minimum number of lines that sweep all marks equals the maximum number of marks no two of which share a row or column.

Stable matching: when both sides have preferences

In the stable marriage problem there are n proposers and n receivers; everyone ranks everyone on the other side. A matching is stable if there is no blocking pair: a proposer and a receiver who each prefer the other to their current partners. Instability matters in practice: a medical resident and a hospital who would both rather be together will break the assignment.

Gale-Shapley (deferred acceptance) always finds a stable matching:

  1. Every free proposer proposes to the best receiver they have not yet proposed to.
  2. A receiver keeps the best proposal received so far and rejects the others (the rejected proposers become free again).
  3. Repeat until nobody is free.

It stops after at most n² proposals. The result is proposer-optimal: every proposer gets the best partner they can have in any stable matching, while receivers get their worst possible stable partner. This is why the real-world National Resident Matching Program lets the side whose preferences should dominate propose.

Python Gale-Shapley with a stability check

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Stability is a different goal from maximum size or maximum total happiness. A stable matching always exists for the one-to-one bipartite problem (a surprisingly strong result), but in the "stable roommates" version with a single group of people it may not.

Summary of how the results connect

flowchart TD
    M["Maximum matching"] --> H["Hall: left side fully matched iff no violator"]
    M --> K["König: max matching = min vertex cover"]
    K --> I["Max independent set = V - min cover"]
    M --> E["Gallai: min edge cover = V - max matching"]
    M -.-> S["Stable matching: preferences, a separate goal"]

Hall, König and Gallai all follow from augmenting paths; Gale-Shapley answers a different question.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. Hall's condition requires that for every subset S of the left side,

    A subset of workers needs at least as many distinct jobs among them as there are workers; if every subset passes, all left vertices can be matched.
  2. 2. In a bipartite graph the maximum matching has 7 edges. How large is a minimum vertex cover?

    König's theorem states the two sizes are equal in bipartite graphs.
  3. 3. What is a blocking pair in the stable marriage problem?

    A blocking pair would abandon their partners for each other, so a stable matching must have none.
  4. 4. Who is better off in Gale-Shapley with proposers proposing?

    The outcome is proposer-optimal and receiver-pessimal among all stable matchings.

Summary

  • Hall's theorem: the left side can be fully matched iff every subset S has |N(S)| ≥ |S|; a violator proves impossibility.
  • Regular bipartite graphs have perfect matchings, which yields König's edge-coloring theorem.
  • König's theorem: in bipartite graphs maximum matching = minimum vertex cover, and the cover can be read off alternating-path reachability.
  • Gale-Shapley always produces a stable matching in at most n² proposals and favors the proposing side.

Next: Planar Graphs and Euler's Formula