Hall's Theorem and König–Egerváry

The question

Five applicants, $a$ to $e$, and five jobs, $1$ to $5$. An edge joins an applicant to each job they are qualified for:

Can every applicant get a different job they are qualified for? In the language of module 10: does $H$ have a matching that saturates $X$, one that covers every vertex of $X$?

The answer is no. The best you can do is four. But "I tried and failed" is not an answer in a proof course. Someone has to be convinced that no assignment of all five exists, without watching you try all of them. This module is about that kind of evidence: a short object, a certificate, that proves the answer in both directions. A matching proves "yes". This module finds what proves "no".

Throughout, an $X,Y$-bigraph is a bipartite graph with a fixed bipartition $X\cup Y$. For $S\subseteq X$, the neighborhood $N(S)$ is the set of vertices of $Y$ adjacent to at least one vertex of $S$.

Before Hall: matchings and Berge's theorem

This module builds on module 10. If you have not taken it, here is all of it that is used below.

• A matching is a set of edges, no two sharing a vertex. It saturates a vertex that lies on one of its edges.
• A matching is maximum if no matching has more edges, and maximal if no edge can be added to it. Every maximum matching is maximal; the converse fails (in a path with three edges, the middle edge alone is maximal but not maximum).
• For a matching $M$, an $M$-alternating path uses edges that are alternately outside and inside $M$. An $M$-augmenting path is an alternating path whose two ends are both unsaturated. Swapping the edges along it (outside edges in, inside edges out) gives a matching with one more edge.

Berge's theorem (1957). A matching $M$ is maximum if and only if there is no $M$-augmenting path.

Proof. If an augmenting path exists, swapping along it gives a larger matching, so $M$ is not maximum. Conversely, suppose $M$ is not maximum, and let $M^{\prime }$ be a larger matching. In the edges that belong to exactly one of $M$ and $M^{\prime }$, every vertex has degree at most 2, so these edges form paths and even cycles that alternate between $M$ and $M^{\prime }$. Cycles use equally many edges of each, and $|M^{\prime }|>|M|$, so some path has more edges of $M^{\prime }$ than of $M$. Its first and last edges are in $M^{\prime }$, and its ends are unsaturated by $M$: an $M$-edge at an end would either lie in the symmetric difference too (so the path would continue) or belong to $M^{\prime }$ as well (so two $M^{\prime }$-edges would meet at that end). So it is an $M$-augmenting path. $◻$

The naive approach, and where it wastes work

There are only finitely many ways to assign jobs, so a computer can list them all:

from itertools import combinations, chain

H = {"a": {"1", "2"}, "b": {"1", "2"}, "c": {"1", "2", "3"}, "d": {"3"}, "e": {"3", "4", "5"}}
X = list(H)
Y = ["1", "2", "3", "4", "5"]

def all_matchings(adj, xs):
    """Every matching of an X,Y-bigraph, as dicts x -> y (brute force, for checking only)."""
    found = []
    def extend(i, used, current):
        if i == len(xs):
            found.append(dict(current))
            return
        extend(i + 1, used, current)                  # x_i stays unmatched
        for y in sorted(adj[xs[i]] - used):
            current[xs[i]] = y
            extend(i + 1, used | {y}, current)
            del current[xs[i]]
    extend(0, set(), {})
    return found

matchings = all_matchings(H, X)
assert max(len(m) for m in matchings) == 4
assert not any(len(m) == 5 for m in matchings)
assert sum(len(adj) for adj in H.values()) == 11

That settles $H$, but it is not a proof anyone can check by reading. It is also hopeless at scale: with 30 applicants the list is astronomically long. And it wastes work in a specific way: it re-examines the same doomed corner of the graph in every assignment. Look at $a$, $b$, $c$ and $d$. Between them they are qualified for only three jobs, $\{1,2,3\}$. Four people cannot fill three jobs with one person each. That single observation rules out every assignment at once, and anyone can check it in a few seconds.

Hall's condition

The observation generalizes. If a matching saturates $X$, it sends the vertices of any $S\subseteq X$ to $|S|$ distinct vertices, all of them in $N(S)$. So:

Hall's condition. For every subset $S\subseteq X$, $|N(S)|\ge |S|$.

A set $S$ with $|N(S)|<|S|$ is a Hall violator. One violator is a certificate that no matching saturates $X$, and checking it costs one neighborhood computation. That half is easy (it is the "only if" direction below). The theorem is the other half: violators are the only obstruction.

The quantifier "for every $S$" is the whole content of the condition. Checking it for $S=X$ alone is not enough:

In $H$, a computer can check all $2^5-1=31$ nonempty subsets of $X$:

def N(adj, S):
    return set().union(*(adj[x] for x in S))

def subsets(xs):
    return chain.from_iterable(combinations(xs, r) for r in range(1, len(xs) + 1))

violators = [set(S) for S in subsets(X) if len(N(H, S)) < len(S)]
assert violators == [{"a", "b", "c", "d"}]
assert N(H, {"a", "b", "c", "d"}) == {"1", "2", "3"}

So $H$ has exactly one violator, the set you spotted by eye. But checking all subsets is the same exponential search as before. Hall's theorem would be little use if finding a violator required it. The proof below shows it doesn't: the search that fails to grow a matching hands you the violator.

The alternating search, traced on $H$

Start from a maximum matching. In $H$ one is $M=\{a1,b2,c3,e4\}$, and $d$ is the only unsaturated vertex of $X$. Recall from module 10 that an $M$-alternating path uses edges that are alternately outside and inside $M$, and that (Berge) $M$ is maximum exactly when no $M$-augmenting path exists.

Explore from $d$ along alternating paths. From a vertex of $X$, leave by any edge not in $M$. From a vertex of $Y$, leave by its matching edge. Let $Z$ be everything reached:

• from $d$, the only edge is $d3$ (not in $M$): reach $3$;
• $3$ is matched to $c$: reach $c$;
• from $c$, non-matching edges $c1$ and $c2$: reach $1$ and $2$;
• $1$ is matched to $a$, $2$ to $b$: reach $a$ and $b$;
• from $a$ and $b$, every non-matching edge leads back to $1$ or $2$, already reached. Stop.

The search found no unsaturated vertex of $Y$, so no augmenting path starts at $d$, as Berge promised for a maximum matching. Now read off $S=Z\cap X=\{a,b,c,d\}$ and $T=Z\cap Y=\{1,2,3\}$: it is exactly the violator, with $N(S)=T$.

M = {"a": "1", "b": "2", "c": "3", "e": "4"}
Z = {"d", "3", "c", "1", "a", "2", "b"}               # the trace above
S = {v for v in Z if v in H}
T = Z - S
assert N(H, S) == T and len(S) == len(T) + 1
assert all(y in M.values() for y in T)                 # every vertex of T is saturated...
assert {x for x, y in M.items() if y in T} == S - {"d"}   # ...by a partner in S

That was not luck. It is the proof.

Why it works: Hall's theorem, proved

Here is the proof written the way a graded solution should be. Read it once for the argument and once for how it is built.

Proof. Necessity. Suppose a matching $M$ saturates $X$, and let $S\subseteq X$. The $M$-partners of the vertices of $S$ are $|S|$ distinct vertices, each adjacent to a vertex of $S$, so $|N(S)|\ge |S|$.

Sufficiency. We prove the contrapositive: if no matching saturates $X$, we exhibit a violator. Let $M$ be a maximum matching. It does not saturate $X$, so some $u\in X$ is unsaturated. Let $Z$ be the set of vertices reachable from $u$ by $M$-alternating paths, and let $S=Z\cap X$ and $T=Z\cap Y$.

1. Every vertex of $T$ is saturated by $M$. An unsaturated $y\in T$ would end an $M$-alternating path from the unsaturated $u$, which is an $M$-augmenting path. By Berge's theorem that contradicts the fact that $M$ is maximum.
2. $M$ matches $T$ onto $S-\{u\}$. An alternating path that reaches $y\in T$ continues along $y$'s matching edge, so $y$'s partner is in $S$. Conversely, every $x\in S-\{u\}$ was reached by arriving along its matching edge, from a vertex of $T$. So $|S|=|T|+1$.
3. $N(S)=T$. If $x\in S$ and $xy$ is an edge, then either $xy\in M$, and $y\in T$ by step 2, or $xy\notin M$, and the alternating path to $x$ extends to $y$, so $y\in T$. Hence $N(S)\subseteq T$. The reverse inclusion holds because each vertex of $T$ was reached from a vertex of $S$.

So $|N(S)|=|T|=|S|-1<|S|$, and $S$ is a violator. $◻$

Proof moves used here. The same moves recur all semester:

• Extremal choice. It starts from a maximum matching, which turns "no augmenting path" into a usable fact (step 1). A proof that starts from an arbitrary matching gets stuck there.
• Contrapositive, made constructive. "No matching implies a violator" is proved by building the violator, not by assuming Hall's condition and arguing vaguely towards a matching.
• Both inclusions. Step 3 proves $N(S)\subseteq T$ and $T\subseteq N(S)$ separately. The first is the one students skip, and it is where the definition of the search is used.

The marriage corollary

A graph is $k$-regular if every vertex has degree $k$.

Corollary. For $k\ge 1$, every $k$-regular $X,Y$-bigraph has a perfect matching.

Proof. Count edges from each side: every edge has one end in $X$ and one in $Y$, so $k|X|=|E|=k|Y|$, and $|X|=|Y|$ since $k\ge 1$. So a matching saturating $X$ is perfect, and by Hall's theorem it suffices to check Hall's condition. Let $S\subseteq X$. Exactly $k|S|$ edges leave $S$, and all of them end in $N(S)$. The vertices of $N(S)$ have degree $k$, so they absorb at most $k|N(S)|$ edge ends. Hence $k|S|\le k|N(S)|$, and $|N(S)|\ge |S|$. $◻$

The proof counts one set of edges in two ways, from $S$ and from $N(S)$. Double counting is the standard way to verify Hall's condition for a whole family of graphs at once. Note what the proof uses: $k\ge 1$ (for $k=0$ the count no longer forces $|X|=|Y|$, and an edgeless graph has no perfect matching anyway) and that every vertex of $N(S)$ has degree at most $k$. The argument works for multigraphs too, since it only counts edges.

A close relative of double counting is averaging. If two sums over the same index set satisfy $a_1+\dots +a_r<b_1+\dots +b_r$, then $a_i<b_i$ for at least one $i$, since otherwise adding $a_i\ge b_i$ over all $i$ would reverse the inequality. It does not follow for every $i$: $1+3<2+3$, yet $3=3$.

The 3-cube $Q_3$ (eight vertices, the 3-bit strings, adjacent when they differ in one bit) is 3-regular and bipartite, split by the parity of the number of ones, so it has a perfect matching:

Q3 = {v: {v ^ (1 << i) for i in range(3)} for v in range(8)}
even = [v for v in Q3 if bin(v).count("1") % 2 == 0]
perfect = [m for m in all_matchings(Q3, even) if len(m) == 4]
assert all(len(Q3[v]) == 3 for v in Q3) and len(perfect) == 9

Covers, and König–Egerváry

A vertex cover is a set $Q$ of vertices touching every edge. Write ${\alpha }^{\prime }(G)$ for the size of a maximum matching and $\beta (G)$ for the size of a minimum vertex cover. In every graph ${\alpha }^{\prime }(G)\le \beta (G)$: the edges of a matching share no vertex, so a cover needs a different vertex for each of them.

So a matching and a cover of the same size certify each other: the matching is maximum and the cover is minimum. For bipartite graphs such a pair always exists:

Proof. Let $M$ be a maximum matching of an $X,Y$-bigraph $G$, let $U$ be the set of $M$-unsaturated vertices of $X$, and let $Z$ be the set of vertices reachable by $M$-alternating paths starting anywhere in $U$. Let $S=Z\cap X$, $T=Z\cap Y$, and $$Q=(X-S)\cup T.$$

Claim 1: $Q$ is a vertex cover. Take an edge $xy$ with $x\in X$. If $x\notin S$, then $x\in Q$. If $x\in S$, then $y\in N(S)$, and step 3 of Hall's proof (which works for $Z$ grown from all of $U$) gives $y\in T\subseteq Q$.

Claim 2: $Q$ has at most $|M|$ vertices. By step 1, every vertex of $T$ is saturated, and by step 2 its partner lies in $S$. Every vertex of $X-S$ is saturated too, because $U\subseteq S$. So each vertex of $Q$ is saturated, and no edge of $M$ has both ends in $Q$: an edge of $M$ with its $Y$ end in $T$ has its $X$ end in $S$. So distinct vertices of $Q$ lie on distinct edges of $M$.

Conclusion. $\beta (G)\le |Q|\le |M|={\alpha }^{\prime }(G)\le \beta (G)$, so equality holds throughout: $M$ and $Q$ certify each other. $◻$

In $H$, $U=\{d\}$ and the trace above gives $Q=\{e\}\cup \{1,2,3\}$, four vertices for four matching edges:

Q = (set(X) - S) | T
edges = [(x, y) for x in H for y in H[x]]
assert Q == {"e", "1", "2", "3"} and all(x in Q or y in Q for x, y in edges)
assert len(Q) == len(M) == 4

Bipartiteness is needed. In the triangle $K_3$, ${\alpha }^{\prime }=1$ but every cover needs two vertices.

Optional: Gallai's identities and the four numbers

Not needed for the lab. Two more parameters complete the picture: $\alpha (G)$, the size of a largest independent set (no two adjacent), and ${\beta }^{\prime }(G)$, the size of a smallest edge cover (edges touching every vertex). Gallai's identities hold in every graph with $n$ vertices:

• $\alpha (G)+\beta (G)=n$, because a set is independent exactly when its complement is a vertex cover;
• ${\alpha }^{\prime }(G)+{\beta }^{\prime }(G)=n$ if $G$ has no isolated vertices: add one edge per unsaturated vertex to a maximum matching to get an edge cover, and keep one edge per star of a minimum edge cover to get a matching (we state the star structure without proof).

With König–Egerváry, a bipartite graph without isolated vertices has $\alpha ={\beta }^{\prime }$. In $H$, $n=10$:

V = X + Y
def is_independent(q):
    return all(not (x in q and y in q) for x, y in edges)
alpha = max(k for k in range(len(V) + 1) for q in combinations(V, k) if is_independent(set(q)))
beta_prime = min(k for k in range(1, len(edges) + 1)
                 for f in combinations(edges, k) if set(chain.from_iterable(f)) == set(V))
assert (alpha, beta_prime) == (6, 6) and alpha + 4 == 10 and 4 + beta_prime == 10

What a certificate saves

The theorems turn an exponential question into short evidence that is cheap to check, in both directions. For $|X|=|Y|=n$, compare the number of subsets Hall's condition quantifies over, $2^n-1$, with the size of a violator certificate (at most $2n-1$ vertices: $S$ and $N(S)$) and of a matching–cover pair (at most $2n$ edges and vertices):

assert 2 ** 5 - 1 == 31 and 2 ** 20 - 1 == 1_048_575
assert round((2 ** 50 - 1) / 1e15, 2) == 1.13

Finding the certificate is also cheap. Each alternating search looks at each edge at most once, so growing a maximum matching one augmenting path at a time takes at most $n$ searches: time $O(n·|E|)$ in the worst case (Kuhn's method, the bipartite case of module 10's augmenting paths). Hopcroft and Karp's algorithm improves this to $O(\sqrt{n}|E|)$. Checking a certificate costs one pass over the edges.

A problem that looks different

On a $6\times 6$ board, some squares are blocked. You want to place six rooks on open squares so that no two share a row or a column. Sometimes it is impossible. When it is, what short evidence would convince a skeptic, and why must such evidence always exist? Nothing in the question mentions applicants or jobs. The lab's last exercise is a different problem that also hides its structure, and it will not say which idea it needs either.

Practise

The lab runs in your browser. Your code grows the alternating search frame by frame and reads a violator off where it stops, then builds a minimum cover and sees a tempting shortcut fail. Half of the lab is proofs: assemble one from its steps (with decoys), find the false step in a wrong one, and write one for a problem that names no technique.

Recap

• You can now: state Hall's theorem with its quantifier; prove it by turning a maximum matching into a violator; verify Hall's condition by double counting; prove König–Egerváry and build the cover; and certify "yes" and "no" answers with short objects.
• Invariant: in the alternating search from the unsaturated vertices of a maximum matching, every reached vertex of $Y$ is saturated and its partner is reached, which gives $|S|=|T|+|U|$; and every neighbor of a reached vertex of $X$ is reached, which gives $N(S)=T$.
• Complexity achieved: a certificate for either answer that is checked in $O(|E|)$ time, found in $O(n·|E|)$ worst-case time, against $2^n-1$ subsets for checking Hall's condition directly.
• Failure mode: stating Hall's condition for $S=X$ only, and in a proof, showing $T\subseteq N(S)$ but never $N(S)\subseteq T$.
• In real software: SciPy's maximum_bipartite_matching (in scipy.sparse.csgraph) uses Hopcroft–Karp; NetworkX's bipartite.to_vertex_cover builds the König cover from a maximum matching.
• Retrieval: module 10 asked when a matching is maximum. Berge's answer, no augmenting path, is exactly step 1 of the proof of Hall's theorem.

Check yourself

After the lab, the tutor will ask you to defend your work out loud:

1. In the proof of Hall's theorem, where exactly is the fact that $M$ is maximum used, and what goes wrong if $M$ is only maximal (no edge can be added)?
2. You have a matching with 7 edges and a vertex cover with 7 vertices in some graph. What do they prove, and does your answer change if the graph is not bipartite?
3. Why does König–Egerváry fail for the triangle, and which step of its proof uses bipartiteness?

Topic list modeled on the public syllabus of UIUC Math 412 (Graph Theory), which follows D. B. West, Introduction to Graph Theory, 2nd ed., Chapters 1–7. All lessons, proofs, examples, code and exercises here are original. This course is independent and not affiliated with or endorsed by the University of Illinois.