Bipartite Graphs and Matchings

⚡ Key Takeaways

A bipartite graph is a graph whose vertices split into two disjoint sets with edges only crossing between them. A matching is a set of edges sharing no endpoints. Key result: König's Theorem and Hall's Marriage Theorem completely characterize when perfect matchings exist and relate maximum matchings to minimum vertex covers. Applies to assignment problems, scheduling, and network flows. Foundations laid by Frobenius (1917), König, and Hall (1935).

💡 The Core Insight

Bipartite structure forbids odd cycles, which makes "augmenting paths" behave perfectly. A matching is maximum if and only if no augmenting path exists, and in bipartite graphs these paths can be found greedily. This turns matching into a problem of local search along alternating paths, and the obstruction to a perfect matching is always a single "deficient" set, never something subtle.

DefinitionBipartite Graph

A graph $G=(V,E)$ is bipartite with bipartition $(X,Y)$ if

1

\quad V = X \cup Y,\quad X \cap Y = \varnothing,\quad \forall\, e=\{u,v\}\in E:\ (u\in X \wedge v\in Y).

Derivation hint: directly encode "every edge crosses the partition" as a logical constraint on endpoints. Here $X,Y$ are the two parts (or color classes). The numbers $|X|$ and $|Y|$ are the sizes of the sides.

TheoremCharacterization by Odd Cycles (König 1916)

A graph is bipartite if and only if it contains no cycle of odd length.

2

\quad G \text{ bipartite} \iff \forall \text{ cycles } C \subseteq G:\ |C| \equiv 0 \pmod 2.

Derivation hint: 2-color the graph by BFS parity; a conflict appears exactly when an odd closed walk forces a vertex to need both colors.

DefinitionMatching, Maximum, Perfect

A matching $M\subseteq E$ satisfies: no two edges of $M$ share an endpoint.

3

\quad \forall\, e,f\in M,\ e\neq f:\ e\cap f = \varnothing.

Derivation hint: "share no endpoint" is just disjointness of the two-element edge sets.

$M$ is maximum if no matching has more edges: $|M|=\nu(G)$ , where $\nu(G)$ is the matching number.
$M$ is perfect if every vertex is matched: $2|M| = |V|$ .
A vertex covered by $M$ is saturated; otherwise exposed/free.

DefinitionVertex Cover and Covering Number

A vertex cover is a set $U\subseteq V$ touching every edge:

4

\quad \forall\, e=\{u,v\}\in E:\ u\in U \ \vee\ v\in U.

Derivation hint: a cover must "hit" each edge, so at least one endpoint lies in $U$ . The minimum size of a vertex cover is $\tau(G)$ .

TheoremHall's Marriage Theorem (1935)

Let $G$ be bipartite with parts $(X,Y)$ . There exists a matching saturating $X$ iff for every subset $S\subseteq X$ ,

5

\quad |N(S)| \ \ge\ |S|,

where $N(S)=\{y\in Y:\exists\, x\in S,\ \{x,y\}\in E\}$ is the neighborhood of $S$ . Derivation hint: necessity is counting; sufficiency follows by augmenting-path induction or by reducing to König's theorem.

TheoremKönig's Theorem (1931)

In any bipartite graph, the maximum matching number equals the minimum vertex cover number:

6

\quad \nu(G) = \tau(G).

Derivation hint: build a vertex cover of size $\nu(G)$ from an alternating-path reachability argument; weak duality gives $\nu\le\tau$ always.

DefinitionDeficiency Version (König–Ore)

The maximum matching size obeys the deficiency formula:

7

\quad \nu(G) = |X| - \max_{S\subseteq X}\big(|S|-|N(S)|\big).

Derivation hint: the term $\max(|S|-|N(S)|)$ measures the worst Hall-violating set; subtract this "deficiency" from $|X|$ .

ProofHall's Theorem via Augmenting Paths

We prove the nontrivial direction: if $|N(S)|\ge|S|$ for all $S\subseteq X$ , then $X$ can be saturated.

Step 1 — Setup. Let $M$ be a maximum matching. Suppose for contradiction some $x_0\in X$ is exposed. We build a set $S$ violating Hall's condition.

Step 2 — Alternating tree. Grow an alternating path from $x_0$ : edges alternate between non-matching (from $X$ to $Y$ ) and matching (from $Y$ back to $X$ ). Let

8

\quad S = \{x\in X : x \text{ reachable from } x_0 \text{ via alternating path}\},\quad T = N_{\text{reached}}(S)\subseteq Y.

Derivation hint: collect exactly the vertices the alternating search touches on each side.

Step 3 — Structure of reached vertices. Every $y\in T$ is matched (else we found an augmenting path from $x_0$ to $y$ , contradicting maximality of $M$ ), and its match lies in $S$ . Hence $M$ gives a bijection between $T$ and $S\setminus\{x_0\}$ , so

9

\quad |T| = |S| - 1.

Derivation hint: every matched $y\in T$ pairs to a distinct reachable $x\in S$ , and $x_0$ alone is unmatched.

Step 4 — $N(S)=T$ . Any neighbor $y$ of some $x\in S$ is reachable (extend the alternating path), so $N(S)\subseteq T$ ; trivially $T\subseteq N(S)$ . Thus $|N(S)|=|T|=|S|-1<|S|$ , violating Hall's condition — contradiction. Therefore no exposed vertex exists and $X$ is saturated. $\blacksquare$

∎

ProofKönig's Theorem from a Maximum Matching

Let $M$ be a maximum matching. Let $U\subseteq X$ be the exposed vertices of $X$ . Let $Z$ be the set of all vertices reachable from $U$ by alternating paths. Define

10

\quad C = (X\setminus Z)\ \cup\ (Y\cap Z).

Derivation hint: take unreachable $X$ -vertices plus reachable $Y$ -vertices — exactly the "blocked" side of each matching edge.

Claim 1 — $C$ is a vertex cover. Any edge $\{x,y\}$ with $x\in Z\cap X$ : its other end $y$ must be in $Z$ (reachability extends), so $y\in C$ . If $x\notin Z$ , then $x\in C$ . So every edge is covered.

Claim 2 — $|C|=|M|$ . No edge of $M$ connects $X\setminus Z$ to $Y\cap Z$ (that would extend reachability), and every vertex of $C$ is matched (exposed $X$ -vertices are in $Z$ , hence excluded; exposed $Y$ -vertices are unreachable). Each matching edge contributes exactly one vertex to $C$ . Hence $|C|=|M|=\nu(G)$ . Since $\tau\ge\nu$ always (each matching edge needs its own cover vertex) and we exhibited a cover of size $\nu$ , we get $\tau=\nu$ . $\blacksquare$

∎

mathematician · Philip Hall | 1904–1982

Philip Hall, a British group theorist at Cambridge, proved the Marriage Theorem in 1935 while studying systems of distinct representatives. Though best known for deep contributions to finite group theory (Hall subgroups, the Hall–Higman theorem), his combinatorial result became a cornerstone of matching theory. The evocative "marriage" framing — matching people to acceptable partners — popularized the abstract statement, and the theorem's many equivalent forms (König, Menger, max-flow) reveal it as one face of a single duality principle.

🧠 Intuition

Picture jobs ( $X$ ) and workers ( $Y$ ), with an edge meaning "this worker can do this job." A perfect assignment is a perfect matching. Hall's condition says: assignment fails only if some group of $k$ jobs collectively can be done by fewer than $k$ workers — a genuine bottleneck. König's duality is the accountant's version: the fewest "checkpoints" (vertices) needed to monitor every connection equals the most independent connections you can run simultaneously. The augmenting path is the trick that fixes a suboptimal assignment: find a free job, follow a chain that re-shuffles existing assignments, and end at a free worker — flipping the chain increases the match by one.

Figure

An alternating/augmenting path in a bipartite graph. Bold gold edges are in matching M; the dashed path augments it.

```svg

```

ExampleChecking Hall's Condition Numerically

Given: Jobs $X=\{a,b,c\}$ , workers $Y=\{1,2,3\}$ , with capability edges: $a$ –{1,2}, $b$ –{1}, $c$ –{1}.

Step 1 — Test small sets. $|N(\{a\})|=2\ge1$ . $|N(\{b\})|=1\ge1$ . Good.

Step 2 — Test the suspicious set. Take $S=\{b,c\}$ : $N(S)=\{1\}$ , so $|N(S)|=1$ but $|S|=2$ .

Step 3 — Hall's condition fails. Since $1<2$ , no matching saturates $X$ .

Step 4 — Maximum matching size. Deficiency $=\max(|S|-|N(S)|)=|\{b,c\}|-|\{1\}|=1$ . By [7]:

\nu = |X|-\text{def} = 3-1 = 2.

Answer: $\boxed{\nu=2 \text{ (no perfect matching; one job unfillable)}}$

ExampleVerifying König Duality

Given: Bipartite graph $X=\{x_1,x_2\}$ , $Y=\{y_1,y_2\}$ with edges $x_1y_1, x_1y_2, x_2y_1$ (a "path-plus" shape).

Step 1 — Find a maximum matching. Take $M=\{x_1y_2,\ x_2y_1\}$ . Both $X$ -vertices saturated; $|M|=2$ .

Step 2 — Is it maximum? Only 4 vertices; a matching of size 2 is perfect, so $\nu=2$ .

Step 3 — Find a minimum vertex cover. $C=\{x_1,y_1\}$ : edge $x_1y_1$ hit by $x_1$ , $x_1y_2$ by $x_1$ , $x_2y_1$ by $y_1$ . Size $2$ . No single vertex covers all 3 edges, so $\tau=2$ .

Step 4 — Confirm [6]. $\nu = \tau = 2$ . ✓

Answer: $\boxed{\nu=\tau=2,\ \text{perfect matching exists}}$

⚠️ Common mistake

Hall's condition is on $X$ , not symmetric. A matching saturating $X$ may exist while $Y$ has exposed vertices (when $|Y|>|X|$ ). For a perfect matching you also need $|X|=|Y|$ , and then checking Hall on $X$ suffices. Also: König's theorem ( $\nu=\tau$ ) holds only for bipartite graphs. In general graphs $\nu\le\tau\le 2\nu$ , and the gap can be real.

Counterexample

König fails in general graphs. Take the triangle $K_3$ (odd cycle, not bipartite). Maximum matching has $\nu=1$ (one edge; the third vertex is left out). But minimum vertex cover needs $\tau=2$ vertices, since one vertex leaves an uncovered edge. Here $\nu=1\ne 2=\tau$ , so duality breaks precisely because $K_3$ has an odd cycle.

connection

Bipartite matching is the combinatorial heart of Max-Flow Min-Cut Theorem: model the matching as a flow network with unit capacities, and an integral max flow equals the maximum matching, while a min cut yields a minimum vertex cover — giving König's theorem as a corollary. It is one instance of Menger's Theorem (vertex-disjoint paths) and of LP duality, since the bipartite matching polytope is integral (the constraint matrix is totally unimodular). The weighted version connects to The Assignment Problem and the Hungarian algorithm, and the structural theory generalizes via Tutte's Theorem for matchings in arbitrary graphs.

🔬 Where this appears

⏳ History

- 1912: Frobenius initiates the algebraic study of bipartite structures, examining when a 0–1 matrix has a nonzero permanent (equivalent to a perfect matching).

- 1916: Dénes König characterizes bipartiteness by the absence of odd cycles, founding graph-theoretic matching.

- 1917: Frobenius proves the determinant/permanent condition for perfect matchings in bipartite graphs.

- 1931: König proves the min–max theorem

\nu=\tau

for bipartite graphs (also derived independently by Egerváry in weighted form the same year).

- 1935: Philip Hall publishes the Marriage Theorem on systems of distinct representatives.

- 1947: Tutte generalizes to arbitrary graphs with the Tutte–Berge formula's precursor.

- 1955: Harold Kuhn introduces the Hungarian algorithm for weighted assignment, crediting König and Egerváry.

- 1965: Jack Edmonds gives a polynomial algorithm for general (non-bipartite) matching via blossoms.

- 1973: Hopcroft and Karp give an

O(\sqrt{V}\,E)

algorithm for maximum bipartite matching, still a benchmark.

- 1990: Karp, Vazirani & Vazirani analyze online bipartite matching (the RANKING algorithm, competitive ratio

1-1/e

).

open-problem

While exact bipartite matching is solved efficiently, several frontiers remain active. Online bipartite matching with stochastic arrivals: closing the gap between known competitive ratios (e.g., beating $1-1/e$ under various arrival models) is ongoing. Dynamic matching: maintaining a near-maximum matching under edge insertions/deletions with low update time is a major area, with conditional lower bounds. Counting perfect matchings (the permanent) is $\#P$ -hard even for bipartite graphs (Valiant 1979), though approximate counting is possible via the Jerrum–Sinclair–Vigoda MCMC algorithm. Finally, the precise communication and streaming complexity of approximating maximum matching remains incompletely understood.

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also