---
title: Bipartite Matching
module: Graphs
moduleNumber: 6
lessonNumber: 14
order: 614
summary: |
  Pairing applicants to jobs, students to slots, files to disks: all are
  **maximum bipartite matching**. We solve it combinatorially with **augmenting
  paths** (Kuhn's algorithm, $O(VE)$), speed it up to $O(E\sqrt V)$ with
  **Hopcroft–Karp**, and uncover the structure behind it — **König's theorem**
  (max matching equals min vertex cover) and **Hall's marriage theorem** (a
  perfect matching exists iff every set has enough neighbors).
topics: [Graphs]
sources:
  - book: CLRS
    ref: "Ch. 26 — Maximum Flow (Bipartite Matching)"
  - book: Erickson
    ref: "Ch. 11 — Applications of Maximum Flow"
  - book: Skiena
    ref: "§6 — Weighted Graph Algorithms (Matching)"
practice:
  - title: 'Maximum Number of Accepted Invitations'
    slug: maximum-number-of-accepted-invitations
    difficulty: Medium
  - title: 'Maximum Compatibility Score Sum'
    slug: maximum-compatibility-score-sum
    difficulty: Medium
  - title: 'Maximum Students Taking Exam'
    slug: maximum-students-taking-exam
    difficulty: Hard
---

A great many assignment problems share one shape: two disjoint groups, a list of
which pairs are compatible, and the wish to pair off as many as possible with no
one used twice. Applicants and jobs, students and exam seats, taxis and riders,
files and disk blocks — each is a **bipartite graph**, and "pair off as many as
possible" is **maximum bipartite matching**. The [previous
lesson](/algorithms/graphs/network-flow) showed this falls out of max-flow as a
unit-capacity special case. This lesson takes matching on its own terms: a direct
combinatorial algorithm, a faster one, and the two theorems that explain _why_
the greedy-looking augmenting trick works.

## The problem

> **Definition (Matching).** A **matching** $M$ in a graph $G = (V, E)$ is a set
> of edges no two of which share an endpoint. A vertex incident to an edge of $M$
> is **matched** (or _saturated_); otherwise it is **free**. A matching is
> **maximum** if no matching has more edges, and **perfect** if every vertex is
> matched.

We restrict to **bipartite** graphs: $V$ splits into two sides $L$ and $R$ with
every edge running between them ($L \to R$, never within a side). The bipartite
structure is what makes the problem tractable; matching in general graphs is also
polynomial but needs Edmonds' far subtler _blossom_ algorithm, which we set aside.

::impl{algo="bipartite_graph"}

$$
% caption: A bipartite graph (left side $L$, right side $R$); the three green edges
%          $L_1 r_1$, $L_2 r_3$, $L_3 r_2$ form a matching of size $3$, leaving
%          $L_4$ and $r_4$ free (no incident matched edge).
\begin{tikzpicture}[
  vtx/.style={circle, draw, minimum size=7mm, font=\small},
  >={Stealth[round]}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \node[vtx] (l1) at (0,3.6) {$L_1$};
  \node[vtx] (l2) at (0,2.4) {$L_2$};
  \node[vtx] (l3) at (0,1.2) {$L_3$};
  \node[vtx, draw=acc, fill=acc!12, line width=1.2pt] (l4) at (0,0) {$L_4$};
  \node[vtx] (r1) at (3.6,3.6) {$r_1$};
  \node[vtx] (r2) at (3.6,2.4) {$r_2$};
  \node[vtx] (r3) at (3.6,1.2) {$r_3$};
  \node[vtx, draw=acc, fill=acc!12, line width=1.2pt] (r4) at (3.6,0) {$r_4$};
  \draw[black] (l1) -- (r2);
  \draw[black] (l2) -- (r1);
  \draw[black] (l3) -- (r3);
  \draw[black] (l4) -- (r3);
  \draw[green, line width=1.5pt] (l1) -- (r1);
  \draw[green, line width=1.5pt] (l2) -- (r3);
  \draw[green, line width=1.5pt] (l3) -- (r2);
  \node[font=\footnotesize] at (0,-0.95) {$L$};
  \node[font=\footnotesize] at (3.6,-0.95) {$R$};
  \node[font=\scriptsize, text=acc] at (1.8,-0.45) {free vertices outlined blue};
\end{tikzpicture}
$$

## Augmenting paths

Every matching algorithm is built on the **augmenting path**, the same idea as
in flow but specialized to alternate on and off the matching.

> **Definition (Alternating / augmenting path).** Relative to a matching $M$, an
> **alternating path** is a path whose edges alternate between $M$ and $E
> \setminus M$. An **augmenting path** is an alternating path that _starts and
> ends at free vertices_.

An augmenting path $P$ has odd length: free, unmatched edge, matched edge,
unmatched edge, $\dots$, unmatched edge, free. It carries one more unmatched edge
than matched edge. So if we **flip** $P$ — delete its matched edges from $M$ and
add its unmatched ones — we get a new matching with exactly one more edge, and it
is still a valid matching because the only vertices whose status changed were the
two formerly-free endpoints. This flip is the matching analogue of pushing flow
along a residual path.

$$
% caption: An augmenting path $L_4\,r_3\,L_3\,r_2$ with free endpoints $L_4, r_2$
%          (blue-outlined): green edges are matched, gray unmatched. Flipping the path
%          grows the matching from size $1$ (left) to size $2$ (right).
\begin{tikzpicture}[
  vtx/.style={circle, draw, minimum size=7mm, font=\small},
  free/.style={circle, draw=acc, line width=1.3pt, fill=acc!12, minimum size=7mm, font=\small},
  >={Stealth[round]}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  % --- before ---
  \begin{scope}
    \node[vtx] (l3) at (0,1.9) {$L_3$};
    \node[free] (l4) at (0,0) {$L_4$};
    \node[free] (r2) at (2.8,1.9) {$r_2$};
    \node[vtx] (r3) at (2.8,0) {$r_3$};
    \draw[green, line width=1.5pt] (l3) -- (r3);
    \draw[black] (l4) -- (r3);
    \draw[black] (l3) -- (r2);
    \node[font=\footnotesize] at (1.4,-1.3) {before};
  \end{scope}
  % --- after ---
  \begin{scope}[xshift=58mm]
    \node[vtx] (l3) at (0,1.9) {$L_3$};
    \node[vtx] (l4) at (0,0) {$L_4$};
    \node[vtx] (r2) at (2.8,1.9) {$r_2$};
    \node[vtx] (r3) at (2.8,0) {$r_3$};
    \draw[black] (l3) -- (r3);
    \draw[green, line width=1.5pt] (l4) -- (r3);
    \draw[green, line width=1.5pt] (l3) -- (r2);
    \node[font=\footnotesize] at (1.4,-1.3) {after};
  \end{scope}
\end{tikzpicture}
$$

The whole theory rests on one fact: the _absence_ of augmenting paths certifies
optimality.

> **Theorem (Berge).** A matching $M$ is maximum **iff** it admits no augmenting
> path.

> **Proof.** ($\Rightarrow$) If $M$ has an augmenting path, flipping it yields a
> larger matching, so $M$ was not maximum. Contrapositive gives one direction.
>
> ($\Leftarrow$) Suppose $M$ is not maximum; let $M^\ast$ be larger. Consider the
> **symmetric difference** $M \oplus M^* = (M \setminus M^*) \cup (M^* \setminus
> M)$. Every vertex touches at most one edge of $M$ and at most one of $M^*$, so in
> $M \oplus M^\ast$ each vertex has degree at most $2$. A graph of maximum degree $2$
> is a disjoint union of **simple paths and cycles**, and along each, edges
> alternate between $M$ and $M^\ast$ (two $M$-edges can never be adjacent). Every
> cycle has equal numbers of $M$- and $M^\ast$-edges. Since $|M^\ast| > |M|$, some
> component is a path with _more_ $M^\ast$-edges than $M$-edges; such a path begins
> and ends with $M^\ast$-edges, so both endpoints are free in $M$ — an augmenting
> path for $M$. $\qed$

This is the soundness/completeness split from the foundations. **Soundness:**
when the algorithm stops (no augmenting path found), Berge's theorem guarantees
the matching really is maximum — an "optimal" verdict is never wrong.
**Completeness:** as long as the matching is suboptimal, an augmenting path
_exists_ to be found, so the algorithm never halts early. Berge's theorem turns
local non-improvability into global optimality.

### A trace on one graph

Take a fixed graph on $L = \{L_1, L_2, L_3, L_4\}$ and $R = \{r_1, r_2, r_3,
r_4\}$ with edges $L_1r_1,\, L_1r_2,\, L_2r_1,\, L_3r_2,\, L_3r_3,\, L_4r_3,\,
L_4r_4$. Start with the empty matching and process left vertices in order,
finding one augmenting path each time. The first two are trivial single edges,
because their targets are free; the third forces a genuine re-route.

- **$L_1$:** the edge $L_1r_1$ reaches a free right vertex. Augment; $M = \{L_1
  r_1\}$.
- **$L_2$:** $L_2$'s only neighbor $r_1$ is taken by $L_1$. Try to re-route $L_1$:
  its other neighbor $r_2$ is free, so the path $L_2 \, r_1 \, L_1 \, r_2$
  augments. Flip it: $M = \{L_2 r_1,\, L_1 r_2\}$, size $2$.
- **$L_3$:** neighbor $r_2$ is taken by $L_1$; $L_1$'s alternate $r_1$ is taken by
  $L_2$; $L_2$ has no other neighbor, so that branch dead-ends. Back at $L_3$, try
  its other neighbor $r_3$ — free. Augment $L_3 r_3$; $M$ has size $3$.
- **$L_4$:** neighbor $r_3$ is taken by $L_3$; $L_3$'s alternate $r_2$ is taken by
  $L_1$; $L_1$'s alternate $r_1$ is taken by $L_2$; $L_2$ dead-ends. Back at
  $L_4$, its other neighbor $r_4$ is free. Augment $L_4 r_4$; $M$ has size $4$.

Every left vertex is matched, so $M$ is perfect and certainly maximum. The trace
below shows the matching after each augmentation; augment 2 rewires an
existing edge rather than merely adding one.

$$
% caption: Four augmentations building a perfect matching. Each panel shows the matching
%          (green) after processing $L_1, L_2, L_3, L_4$ in turn. Augment 2 re-routes:
%          $L_1$ slides from $r_1$ to $r_2$ so $L_2$ can take $r_1$. Free vertices are
%          blue-outlined; gray edges are unmatched.
\begin{tikzpicture}[
  vtx/.style={circle, draw, minimum size=5.5mm, inner sep=0pt, font=\scriptsize},
  free/.style={circle, draw=acc, line width=1pt, fill=acc!12, minimum size=5.5mm, inner sep=0pt, font=\scriptsize},
  >={Stealth[round]}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  % --- Panel 1: after L1 (M = L1r1) ---
  \begin{scope}
    \node[vtx]  (a1) at (0,3.0) {$L_1$};
    \node[free] (a2) at (0,2.0) {$L_2$};
    \node[free] (a3) at (0,1.0) {$L_3$};
    \node[free] (a4) at (0,0.0) {$L_4$};
    \node[vtx]  (b1) at (2.2,3.0) {$r_1$};
    \node[free] (b2) at (2.2,2.0) {$r_2$};
    \node[free] (b3) at (2.2,1.0) {$r_3$};
    \node[free] (b4) at (2.2,0.0) {$r_4$};
    \draw[green, line width=1.4pt] (a1) -- (b1);
    \node[font=\footnotesize] at (1.1,-0.9) {\texttt{after L1}};
  \end{scope}
  % --- Panel 2: after L2 (M = L2r1, L1r2) ---
  \begin{scope}[xshift=42mm]
    \node[vtx]  (c1) at (0,3.0) {$L_1$};
    \node[vtx]  (c2) at (0,2.0) {$L_2$};
    \node[free] (c3) at (0,1.0) {$L_3$};
    \node[free] (c4) at (0,0.0) {$L_4$};
    \node[vtx]  (d1) at (2.2,3.0) {$r_1$};
    \node[vtx]  (d2) at (2.2,2.0) {$r_2$};
    \node[free] (d3) at (2.2,1.0) {$r_3$};
    \node[free] (d4) at (2.2,0.0) {$r_4$};
    \draw[green, line width=1.4pt] (c2) -- (d1);
    \draw[green, line width=1.4pt] (c1) -- (d2);
    \node[font=\footnotesize] at (1.1,-0.9) {\texttt{after L2}};
  \end{scope}
  % --- Panel 3: after L3 (add L3r3) ---
  \begin{scope}[xshift=84mm]
    \node[vtx]  (e1) at (0,3.0) {$L_1$};
    \node[vtx]  (e2) at (0,2.0) {$L_2$};
    \node[vtx]  (e3) at (0,1.0) {$L_3$};
    \node[free] (e4) at (0,0.0) {$L_4$};
    \node[vtx]  (f1) at (2.2,3.0) {$r_1$};
    \node[vtx]  (f2) at (2.2,2.0) {$r_2$};
    \node[vtx]  (f3) at (2.2,1.0) {$r_3$};
    \node[free] (f4) at (2.2,0.0) {$r_4$};
    \draw[green, line width=1.4pt] (e2) -- (f1);
    \draw[green, line width=1.4pt] (e1) -- (f2);
    \draw[green, line width=1.4pt] (e3) -- (f3);
    \node[font=\footnotesize] at (1.1,-0.9) {\texttt{after L3}};
  \end{scope}
  % --- Panel 4: after L4 (perfect) ---
  \begin{scope}[xshift=126mm]
    \node[vtx]  (g1) at (0,3.0) {$L_1$};
    \node[vtx]  (g2) at (0,2.0) {$L_2$};
    \node[vtx]  (g3) at (0,1.0) {$L_3$};
    \node[vtx]  (g4) at (0,0.0) {$L_4$};
    \node[vtx]  (h1) at (2.2,3.0) {$r_1$};
    \node[vtx]  (h2) at (2.2,2.0) {$r_2$};
    \node[vtx]  (h3) at (2.2,1.0) {$r_3$};
    \node[vtx]  (h4) at (2.2,0.0) {$r_4$};
    \draw[green, line width=1.4pt] (g2) -- (h1);
    \draw[green, line width=1.4pt] (g1) -- (h2);
    \draw[green, line width=1.4pt] (g3) -- (h3);
    \draw[green, line width=1.4pt] (g4) -- (h4);
    \node[font=\footnotesize] at (1.1,-0.9) {\texttt{after L4}};
  \end{scope}
\end{tikzpicture}
$$

## Kuhn's algorithm

Berge's theorem suggests the algorithm immediately: repeatedly find an augmenting
path and flip it, until none remains. In a bipartite graph the search is
especially clean. Try to match each left vertex $u$ in turn. From $u$, run a DFS
that only ever takes alternating steps: step to a neighbor $v \in R$; if $v$ is
free, we have found the end of an augmenting path — match $u$–$v$ and return; if
$v$ is already matched to some $u'$, recursively try to re-route $u'$ to a
_different_ free partner, and if that succeeds, $v$ is freed for $u$. This is
the **Hungarian** / **Kuhn** augmenting-path method.[^clrs-bm]

```algorithm
caption: $\textsc{Kuhn}(G, L, R)$ — maximum bipartite matching by augmenting paths
number: 1
foreach $v \in R$ do $\text{match}[v] \gets \textsc{nil}$ // who $v$ is matched to
$\text{size} \gets 0$
foreach $u \in L$ do
  reset $\text{seen}[\,\cdot\,] \gets \textsc{false}$ for all $v \in R$
  if $\textsc{TryKuhn}(u)$ then $\text{size} \gets \text{size} + 1$
return $\text{size}$ // and $\text{match}[\cdot]$ holds the matching

// try to match (or re-route) $u$ along an alternating path
function $\textsc{TryKuhn}(u)$:
  foreach $v \in \text{adj}(u)$ do
    if not $\text{seen}[v]$ then
      $\text{seen}[v] \gets \textsc{true}$
      // $v$ free, or its partner can step aside
      if $\text{match}[v] = \textsc{nil}$ or $\textsc{TryKuhn}(\text{match}[v])$ then
        $\text{match}[v] \gets u$
        return $\textsc{true}$
  return $\textsc{false}$
```

> **Correctness.** Each call to $\textsc{TryKuhn}(u)$ from a free $u$ searches
> precisely the alternating paths out of $u$: an unmatched edge $u \to v$, then (if
> $v$ is taken) the matched edge $v \to \text{match}[v]$, then recurse. It returns
> `true` exactly when one of these reaches a free right vertex — an augmenting path
> — and the assignments along the way perform the flip. The $\text{seen}$ flags stop
> the DFS revisiting a right vertex, so each augmentation runs in $O(E)$. A vertex
> once matched stays matched (its partner may change, but it never becomes free), so
> the outer loop drives the size monotonically up. After the loop no free left
> vertex admits an augmenting path; in a bipartite graph every augmenting path has
> a free _left_ endpoint, so _no_ augmenting path remains, and by Berge's theorem
> $M$ is maximum.

$$
% caption: Kuhn's DFS re-routing, read as a zig-zag alternating walk $L_3 \to r_1 \to L_1
%          \to r_2$: $L_3$ wants $r_1$, taken by $L_1$ (green matched edge); the recursion
%          sends $L_1$ to its free alternate $r_2$, liberating $r_1$ for $L_3$. Dashed blue
%          arrows trace the search; after the flip the matching is $L_3 r_1$ and $L_1 r_2$.
\begin{tikzpicture}[
  vtx/.style={circle, draw, minimum size=8mm, font=\small},
  free/.style={circle, draw=acc, line width=1.3pt, fill=acc!12, minimum size=8mm, font=\small},
  >={Stealth[round]}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  % alternating walk laid out as a zig-zag, left column then right column
  \node[free] (l3) at (0,0)   {$L_3$};
  \node[vtx]  (r1) at (4.2,1.5) {$r_1$};
  \node[vtx]  (l1) at (0,3.0)  {$L_1$};
  \node[free] (r2) at (4.2,4.5) {$r_2$};
  % the current matched edge that gets re-routed
  \draw[green, line width=1.6pt] (l1) -- (r1);
  % DFS exploration arrows, bent clear of the green matched edge, no crossings
  \draw[acc, dashed, line width=1.1pt, ->, shorten >=4pt, shorten <=4pt] (l3) to[bend right=12] (r1);
  \draw[acc, dashed, line width=1.1pt, ->, shorten >=4pt, shorten <=4pt] (r1) to[bend right=32] (l1);
  \draw[acc, dashed, line width=1.1pt, ->, shorten >=4pt, shorten <=4pt] (l1) to[bend left=12] (r2);
  \node[font=\footnotesize, text=acc, anchor=west] at (4.7,0.9)  {\texttt{1. try free vertex}};
  \node[font=\footnotesize, text=green!50!black, anchor=west] at (4.7,2.25) {\texttt{2. follow paired edge}};
  \node[font=\footnotesize, text=acc, anchor=west] at (4.7,3.6)  {\texttt{3. reach free alternate}};
\end{tikzpicture}
$$

> **Theorem (Cost).** Kuhn's algorithm runs in $O(VE)$ time and $O(V + E)$ space.

> **Proof.** The outer loop runs $|L| \le V$ times; each iteration is one DFS over
> the residual alternating structure, visiting each edge $O(1)$ times for $O(E)$
> work. Hence $O(VE)$. Storage is the graph plus the $\text{match}$ and
> $\text{seen}$ arrays, $O(V + E)$. $\qed$

In practice Kuhn is much faster than the bound: greedily seeding the matching
first (match each $u$ to any free neighbor before running the loop) and iterating
$L$ from the higher-degree side both cut the constant sharply. For dense graphs
$O(VE)$ can be $O(V^3)$, which is why the next algorithm matters.

::impl{algo="kuhn_matching"}

## Hopcroft–Karp

Kuhn finds **one** augmenting path per phase. Hopcroft–Karp finds a **maximal
set of shortest, vertex-disjoint** augmenting paths per phase, all at once, and
augments along all of them simultaneously. The speedup mirrors Edmonds–Karp's BFS
choice for flow: forcing _shortest_ augmenting paths makes the shortest length
strictly increase across phases, capping the number of phases.[^erickson-hk]

Each **phase** has two steps:

- **BFS** from all free left vertices simultaneously, layering the graph by
  alternating distance, and stopping at the first layer that contains a free right
  vertex. This finds the length $k$ of the _shortest_ augmenting paths.
- **DFS** to greedily extract a _maximal set_ of vertex-disjoint augmenting paths
  of that exact length $k$, flipping each as it is found.

```algorithm
caption: $\textsc{HopcroftKarp}(G, L, R)$ — shortest augmenting paths in phases
number: 2
foreach $u \in L$ do $\text{matchL}[u] \gets \textsc{nil}$
foreach $v \in R$ do $\text{matchR}[v] \gets \textsc{nil}$
$\text{size} \gets 0$
while $\textsc{Bfs}()$ finds at least one augmenting path do // one phase
  foreach free $u \in L$ do
    if $\textsc{Dfs}(u)$ then $\text{size} \gets \text{size} + 1$
return $\text{size}$

// layer by alternating distance; return true if a free right vertex is reached
function $\textsc{Bfs}()$:
  $Q \gets$ empty queue
  foreach $u \in L$ do
    if $\text{matchL}[u] = \textsc{nil}$ then $\text{dist}[u] \gets 0$; enqueue $u$
    else $\text{dist}[u] \gets \infty$
  $\text{found} \gets \textsc{false}$
  while $Q$ nonempty do
    $u \gets$ dequeue
    foreach $v \in \text{adj}(u)$ do
      $w \gets \text{matchR}[v]$ // left vertex across the matched edge
      if $w = \textsc{nil}$ then $\text{found} \gets \textsc{true}$ // reached a free right vertex
      else if $\text{dist}[w] = \infty$ then $\text{dist}[w] \gets \text{dist}[u] + 1$; enqueue $w$
  return $\text{found}$

// extend one shortest augmenting path from $u$, respecting BFS layers
function $\textsc{Dfs}(u)$:
  foreach $v \in \text{adj}(u)$ do
    $w \gets \text{matchR}[v]$
    if $w = \textsc{nil}$ or ($\text{dist}[w] = \text{dist}[u] + 1$ and $\textsc{Dfs}(w)$) then
      $\text{matchL}[u] \gets v$; $\text{matchR}[v] \gets u$ // flip this edge
      return $\textsc{true}$
  $\text{dist}[u] \gets \infty$ // dead end; never revisit
  return $\textsc{false}$
```

> **Theorem (Hopcroft–Karp cost).** The algorithm runs in $O(E \sqrt V)$ time.

> **Proof.** Each phase is one BFS plus one DFS over the whole graph, $O(E)$. Two
> facts bound the phase count. **(i)** The shortest augmenting-path length is
> _strictly larger_ after each phase: the phase augments along a _maximal_ set of
> shortest paths, so any surviving augmenting path must be longer (this is the same
> monotonicity Edmonds–Karp uses). **(ii)** After $\sqrt V$ phases the shortest
> augmenting path has length $\ge \sqrt V$. At that point, if $M$ is the current
> matching and $M^\ast$ a maximum one, $M \oplus M^\ast$ contains $|M^\ast| - |M|$
> vertex-disjoint augmenting paths, each of length $\ge \sqrt V$, so each uses $\ge
> \sqrt V$ vertices; being disjoint, there are at most $V / \sqrt V = \sqrt V$ of
> them. Thus only $\sqrt V$ augmentations — hence $\le \sqrt V$ further phases —
> remain. Total phases $O(\sqrt V)$, total time $O(E \sqrt V)$. $\qed$

For dense bipartite graphs this is a real gain over Kuhn's $O(VE)$, and
Hopcroft–Karp is the standard choice when $V$ is large. It is also
**Dinic's algorithm** specialized to unit-capacity bipartite networks — the
$O(E\sqrt V)$ bound is Dinic's on such networks.

::impl{algo="hopcroft_karp"}

## König's theorem

Augmenting paths solve the matching problem; the next two theorems explain its
**structure**, and both are good interview material in their own right. The first
links matching to its natural dual, the **vertex cover**.[^skiena-konig]

> **Definition (Vertex cover).** A **vertex cover** is a set $C \subseteq V$ of
> vertices such that every edge has at least one endpoint in $C$. A **minimum
> vertex cover** is one of smallest size.

Any matching and any vertex cover are tied by an easy inequality: a vertex cover
must contain at least one endpoint of every matched edge, and those endpoints are
all distinct (matching edges are disjoint), so $|C| \ge |M|$ always — this is
**weak duality**, exactly as $\abs f \le c(S,T)$ was for flow. König's theorem
says that in bipartite graphs the bound is tight.

> **Theorem (König).** In a **bipartite** graph, the size of a maximum matching
> equals the size of a minimum vertex cover:
> $$
> \max_{M}\, |M| \;=\; \min_{C}\, |C|.
> $$

> **Proof.** Weak duality gives $\max|M| \le \min|C|$. For the reverse, take a
> maximum matching $M$ and _build_ a cover of size $|M|$. Let $U \subseteq L$ be
> the free left vertices. Let $Z$ be the set of all vertices reachable from $U$ by
> **alternating paths** (unmatched edge $L \to R$, matched edge $R \to L$,
> repeating). Define
> $$
> C := (L \setminus Z) \;\cup\; (R \cap Z).
> $$
>
> _$C$ is a vertex cover._ Suppose some edge $(\ell, r)$, $\ell \in L$, $r \in R$,
> is covered by neither: $\ell \in Z$ and $r \notin Z$. Since $\ell \in Z$ is
> reachable by an alternating path, extending it by the unmatched-or-matched edge
> $\ell r$ would put $r \in Z$ too — unless $\ell r \in M$, but then $r$ is reached
> from $\ell$ by a matched step, again forcing $r \in Z$. Either way $r \in Z$, a
> contradiction. So every edge is covered.
>
> _$|C| = |M|$._ We show every vertex of $C$ is matched and no matched edge has
> _both_ endpoints in $C$, so $C$ injects into $M$. Every $\ell \in L \setminus Z$
> is matched (a free left vertex lies in $U \subseteq Z$). Every $r \in R \cap Z$
> is matched (an _unmatched_ $r$ reached by an alternating path would be an
> augmenting path, impossible for maximum $M$). Finally, no edge of $M$ joins $L
> \setminus Z$ to $R \cap Z$: if $\ell r \in M$ with $r \in Z$, the alternating
> path to $r$ leaves along its matched edge to $\ell$, putting $\ell \in Z$. Hence
> each cover vertex is the endpoint of a _distinct_ matching edge, giving $|C| \le
> |M|$, and with weak duality $|C| = |M|$. $\qed$

The construction doubles as an _algorithm_ for the
minimum vertex cover. Run Kuhn or Hopcroft–Karp, then one alternating-reachability
BFS from the free left vertices computes $Z$ and reads off $C$. So minimum vertex
cover — **NP-hard in general graphs** — is polynomial on bipartite graphs, solved
through matching. By complementation, $V \setminus C$ is a **maximum independent
set**, also polynomial here.

::impl{algo="konig_vertex_cover"}

$$
% caption: König duality: the maximum matching (green) has size $3$; the minimum vertex
%          cover $\{L_2, r_1, r_3\}$ (blue-filled) also has size $3$, one cover vertex per
%          matched edge.
\begin{tikzpicture}[
  vtx/.style={circle, draw, minimum size=7mm, font=\small},
  cov/.style={circle, draw=acc, line width=1.4pt, fill=acc!18, minimum size=7mm, font=\small},
  >={Stealth[round]}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \node[vtx] (l1) at (0,2.8) {$L_1$};
  \node[cov] (l2) at (0,1.4) {$L_2$};
  \node[vtx] (l3) at (0,0) {$L_3$};
  \node[cov] (r1) at (3.4,2.8) {$r_1$};
  \node[vtx] (r2) at (3.4,1.4) {$r_2$};
  \node[cov] (r3) at (3.4,0) {$r_3$};
  \draw[green, line width=1.5pt] (l1) -- (r1);
  \draw[green, line width=1.5pt] (l2) -- (r2);
  \draw[green, line width=1.5pt] (l3) -- (r3);
  \draw[black] (l2) -- (r1);
  \draw[black] (l2) -- (r3);
  \draw[black] (l1) -- (r3);
  \node[font=\footnotesize] at (0,-0.95) {$L$};
  \node[font=\footnotesize] at (3.4,-0.95) {$R$};
  \node[font=\scriptsize, text=acc] at (1.7,-1.55) {blue marks the cover};
\end{tikzpicture}
$$

## Hall's marriage theorem

The second structural result answers a different question: not _how large_ is the
matching, but _when does it saturate one whole side_. Picture $L$ as people and
$R$ as the partners they would accept; we want everyone in $L$ married. The
obstruction is obvious once stated: if some set $S$ of people collectively know
fewer than $|S|$ acceptable partners, they cannot all be matched. Hall's theorem
says this single obstruction is the _only_ one. Write $N(S)$ for the set of
neighbors of $S$ (every $R$-vertex adjacent to some vertex of $S$).

> **Theorem (Hall's marriage).** A bipartite graph has a matching saturating all
> of $L$ **iff** the **marriage condition** holds:
> $$
> |N(S)| \;\ge\; |S| \qquad \text{for every } S \subseteq L.
> $$

> **Proof.** ($\Rightarrow$) If $L$ is saturated, the $|S|$ matched partners of
> vertices in $S$ are distinct and all lie in $N(S)$, so $|N(S)| \ge |S|$.
>
> ($\Leftarrow$) We show the contrapositive via König. If $L$ is _not_ saturable,
> the maximum matching has size $|M| < |L|$, so by König there is a vertex cover
> $C$ with $|C| = |M| < |L|$. Split $C = C_L \cup C_R$ with $C_L = C \cap L$, $C_R
> = C \cap R$. Consider $S := L \setminus C_L$; then $|S| = |L| - |C_L|$. Because
> $C$ covers every edge and no vertex of $S$ is in $C$, every neighbor of $S$ must
> lie in $C_R$, i.e. $N(S) \subseteq C_R$, so
> $$
> |N(S)| \;\le\; |C_R| \;=\; |C| - |C_L| \;<\; |L| - |C_L| \;=\; |S|.
> $$
> That violates the marriage condition. Contrapositively, the condition forces $L$
> to be saturable. $\qed$

$$
% caption: Hall's condition violated: the set $S = \{L_1, L_2, L_3\}$ (blue-filled) has
%          only two distinct neighbors $N(S) = \{r_1, r_2\}$ (red-outlined), so
%          $|N(S)| = 2 < 3 = |S|$ and no matching can saturate $L$.
\begin{tikzpicture}[
  vtx/.style={circle, draw, minimum size=7.5mm, font=\small},
  inS/.style={circle, draw=acc, line width=1.3pt, fill=acc!16, minimum size=7.5mm, font=\small},
  nbr/.style={circle, draw=red!75!black, line width=1.3pt, minimum size=7.5mm, font=\small},
  >={Stealth[round]}]
  \definecolor{acc}{HTML}{2348F2}
  \node[inS] (l1) at (0,3.0) {$L_1$};
  \node[inS] (l2) at (0,1.5) {$L_2$};
  \node[inS] (l3) at (0,0) {$L_3$};
  \node[nbr] (r1) at (3.6,2.25) {$r_1$};
  \node[nbr] (r2) at (3.6,0.75) {$r_2$};
  \draw[black] (l1) -- (r1);
  \draw[black] (l1) -- (r2);
  \draw[black] (l2) -- (r1);
  \draw[black] (l3) -- (r1);
  \draw[black] (l3) -- (r2);
  \node[font=\footnotesize, text=acc] at (0,-0.95) {\texttt{three in S}};
  \node[font=\footnotesize, text=red!75!black] at (3.6,-0.95) {\texttt{two neighbors}};
\end{tikzpicture}
$$

Hall's theorem is the existence companion to König's optimization statement; the
proof above derives one directly from the other. A corollary handles the
symmetric, fully-balanced case:

> **Corollary (Perfect matching of regular graphs).** Every $d$-regular bipartite
> graph ($d \ge 1$) has a **perfect matching**.

> **Proof.** Regularity forces $|L| = |R|$ (count edges $d|L| = |E| = d|R|$). For
> any $S \subseteq L$, the edges leaving $S$ number $d|S|$ and all land in $N(S)$,
> which absorbs at most $d\,|N(S)|$ edges; so $d|S| \le d\,|N(S)|$, i.e. $|N(S)|
> \ge |S|$. Hall's condition holds, $L$ is saturated, and since $|L| = |R|$ the
> matching is perfect. $\qed$

This corollary explains why a $d$-regular bipartite graph's edges decompose into
$d$ perfect matchings (peel one off, repeat), which underlies, e.g.,
scheduling $d$ conflict-free rounds.

::impl{algo="hall_condition"}

## The reduction to max-flow

The combinatorial view and the flow view describe the same object. The
[max-flow](/algorithms/graphs/network-flow) reduction makes this
explicit, and it is worth carrying out once in full because it explains where the
augmenting-path machinery comes from.

Given a bipartite graph $G = (L \cup R, E)$, build a flow network $G'$:

- add a **source** $s$ and a **sink** $t$;
- for each $\ell \in L$, an edge $s \to \ell$ of capacity $1$;
- for each original edge $\ell r \in E$, a directed edge $\ell \to r$ of capacity
  $1$ (direction $L$ to $R$);
- for each $r \in R$, an edge $r \to t$ of capacity $1$.

Every capacity is $1$. An **integer** $s$–$t$ flow of value $k$ then corresponds
exactly to a matching of size $k$: the unit capacity on $s \to \ell$ lets at most
one middle edge out of $\ell$ carry flow, and the unit capacity on $r \to t$ lets
at most one into $r$, so the saturated middle edges form a set of disjoint pairs
— a matching. Conversely a matching of size $k$ routes $k$ units. Because all
capacities are integral, the integrality theorem for max-flow guarantees an
integer maximum flow exists, so **max-flow value $=$ maximum matching size**.

$$
% caption: Bipartite matching as unit-capacity max-flow. Source $s$ feeds each left
%          vertex (capacity $1$), original edges point $L$ to $R$ (capacity $1$), each
%          right vertex drains to sink $t$ (capacity $1$). Green marks one saturated
%          $s$-$t$ path; the three saturated middle edges are the matching. Every edge
%          has capacity $1$.
\begin{tikzpicture}[
  vtx/.style={circle, draw, minimum size=6.5mm, inner sep=0pt, font=\small},
  trm/.style={circle, draw=acc, fill=acc!12, line width=1.1pt, minimum size=7mm, inner sep=0pt, font=\small},
  >={Stealth[round]}]
  \definecolor{acc}{HTML}{2348F2}
  \definecolor{green}{HTML}{1F9D4D}
  \node[trm] (s) at (-2.6,1.4) {$s$};
  \node[vtx] (l1) at (0,2.8) {$L_1$};
  \node[vtx] (l2) at (0,1.4) {$L_2$};
  \node[vtx] (l3) at (0,0)   {$L_3$};
  \node[vtx] (r1) at (3.2,2.8) {$r_1$};
  \node[vtx] (r2) at (3.2,1.4) {$r_2$};
  \node[vtx] (r3) at (3.2,0)   {$r_3$};
  \node[trm] (t) at (5.8,1.4) {$t$};
  % source edges
  \draw[green, line width=1.4pt, ->, shorten >=2pt] (s) -- (l1);
  \draw[black, ->, shorten >=2pt] (s) -- (l2);
  \draw[black, ->, shorten >=2pt] (s) -- (l3);
  % middle edges (L to R)
  \draw[green, line width=1.4pt, ->, shorten >=2pt] (l1) -- (r1);
  \draw[black, ->, shorten >=2pt] (l1) -- (r2);
  \draw[black, ->, shorten >=2pt] (l2) -- (r1);
  \draw[green, line width=1.4pt, ->, shorten >=2pt] (l2) -- (r2);
  \draw[black, ->, shorten >=2pt] (l3) -- (r2);
  \draw[green, line width=1.4pt, ->, shorten >=2pt] (l3) -- (r3);
  % sink edges
  \draw[green, line width=1.4pt, ->, shorten >=2pt] (r1) -- (t);
  \draw[green, line width=1.4pt, ->, shorten >=2pt] (r2) -- (t);
  \draw[green, line width=1.4pt, ->, shorten >=2pt] (r3) -- (t);
  \node[font=\footnotesize, text=acc] at (1.6,-0.95) {\texttt{every capacity = 1}};
\end{tikzpicture}
$$

An augmenting path in this network alternates forward edges (unused) with
backward residual edges (used) — and on the middle layer that is precisely an
alternating path in $G$: a forward $\ell \to r$ is an unmatched edge, a backward
$r \to \ell$ is a matched edge traversed in reverse. Kuhn's DFS is the flow
algorithm with the $s$ and $t$ plumbing stripped away, and Hopcroft–Karp is Dinic
on this same network. The two views are the same algorithm in different
notation.

## Why not just call max-flow?

Matching reduces to flow, but the dedicated combinatorial algorithms are still
worth having, for several reasons.

- **Simplicity and constants.** Kuhn is a dozen lines of DFS with no residual
  bookkeeping, no source/sink scaffolding, and tiny constants — the practical
  default for the moderate sizes seen in contests and interviews.
- **The right asymptotics.** Hopcroft–Karp's $O(E\sqrt V)$ matches the best
  general bound for this problem and beats a black-box Edmonds–Karp ($O(V E^2)$ is
  far worse here); you get the specialized bound without invoking Dinic by hand.
- **Structure, not just a number.** König and Hall fall straight out of the
  augmenting-path picture, yielding minimum vertex cover, maximum independent
  set, and saturation certificates — outputs the flow value alone does not give.

The flow reduction remains the right tool the moment the problem stops being pure
matching: capacities other than $1$ (a job hiring several applicants), costs on
edges (**minimum-cost** assignment), or many-to-one constraints. Matching is the
special case; flow is the generalization for anything beyond it.

## Weighted, general, and online matching

Unweighted bipartite matching is the entry point to a larger theory; three generalizations are worth knowing by name.

**Weighted matching — the assignment problem.** Put a cost on each edge and ask for the _cheapest_ perfect matching: this is the **assignment problem**, solved by the **Hungarian algorithm** (Kuhn 1955, from Kőnig's and Egerváry's ideas) in $O(V^3)$.[^kuhn-hungarian] It maintains dual variables ("potentials") on the vertices and augments along shortest alternating paths — structurally the same augmenting-path idea, now weighted, and equivalent to min-cost max-flow specialized to unit capacities. It is the standard method for optimal task-to-worker, sensor-to-target, and tracking-association assignments.

**General graphs — Edmonds' blossoms.** Drop the bipartite restriction and the augmenting-path method breaks, because an _odd_ cycle can hide an augmenting path that alternating BFS never finds. Edmonds' **blossom algorithm** (1965) repairs this by contracting each odd cycle (a "blossom") into a single vertex, searching the smaller graph, then lifting the result back — and in doing so gave the field its working definition of "efficient" as polynomial time.[^edmonds-blossom] Micali and Vazirani later pushed general matching to $O(E\sqrt V)$, matching the bipartite bound.

$$
% caption: Why general matching is harder. The odd cycle $b\!-\!c\!-\!d$ (a blossom) hides an
%          augmenting path that alternating search misses; Edmonds' algorithm contracts it
%          to a single vertex, matches the smaller graph, then expands.
\begin{tikzpicture}[font=\small,
  V/.style={circle, draw, minimum size=7mm, inner sep=0pt, font=\small},
  M/.style={line width=1.6pt, draw=acc},
  U/.style={black}]
  \definecolor{acc}{HTML}{2348F2}
  \node[V] (a) at (0,0) {$a$};
  \node[V] (b) at (1.6,0) {$b$};
  \node[V] (c) at (3.0,0.9) {$c$};
  \node[V] (d) at (3.0,-0.9) {$d$};
  \node[V] (e) at (4.4,0) {$e$};
  \draw[M] (a) -- (b);
  \draw[M] (c) -- (d);
  \draw[U] (b) -- (c);
  \draw[U] (b) -- (d);
  \draw[U] (c) -- (e);
  \node[font=\scriptsize, acc] at (2.6,-1.7) {blossom b-c-d: contract, match, expand};
\end{tikzpicture}
$$

**Online and streaming.** When one side arrives over time and must be matched irrevocably on arrival — ad impressions to advertisers, riders to drivers — no algorithm can match the offline optimum. The **RANKING** algorithm (Karp, Vazirani, Vazirani 1990) fixes a random priority over the offline side and greedily matches each arrival to its highest-priority free neighbor, achieving a competitive ratio of $1 - 1/e \approx 0.632$, which is provably optimal for online bipartite matching.[^kvv] This result launched the whole field of online matching that underlies modern ad-allocation systems.

All three build on the augmenting path from this lesson: weighted matching augments with costs, general matching augments through contracted blossoms, and online matching gives up augmentation entirely for a randomized greedy rule.

## Takeaways

- A **matching** is a set of pairwise-disjoint edges; in a **bipartite** graph we
  want a **maximum** one, and the whole theory turns on the **augmenting path**
  (alternating, free-to-free), whose flip grows $M$ by one.
- **Berge's theorem:** $M$ is maximum **iff** it has no augmenting path — the
  soundness (stops only at optimum) and completeness (always improvable until
  optimum) of every augmenting-path algorithm.
- **Kuhn's** augmenting-path DFS runs in $O(VE)$; **Hopcroft–Karp** batches
  shortest, disjoint augmenting paths per phase for $O(E\sqrt V)$, the
  unit-capacity specialization of Dinic.
- **König's theorem:** in bipartite graphs **max matching $=$ min vertex cover**,
  giving a polynomial minimum vertex cover (NP-hard in general) and, by
  complement, maximum independent set.
- **Hall's marriage theorem:** $L$ is fully matchable **iff** $|N(S)| \ge |S|$ for
  all $S \subseteq L$; it yields perfect matchings for $d$-regular bipartite
  graphs and is König's dual face.

[^clrs-bm]: **CLRS**, Ch. 26 — Maximum Flow: bipartite matching as unit-capacity flow, and the augmenting-path method underlying Kuhn's algorithm.
[^erickson-hk]: **Erickson**, Ch. 11 — Applications of Maximum Flow: matching, vertex cover, and the shortest-augmenting-path speedup behind Hopcroft–Karp / Dinic.
[^skiena-konig]: **Skiena**, §6 — Weighted Graph Algorithms: bipartite matching in practice, and the matching / vertex-cover duality (König).
[^kuhn-hungarian]: **Kuhn, H. W.** (1955), "The Hungarian method for the assignment problem," _Naval Research Logistics Quarterly_ 2, 83–97 — $O(V^3)$ minimum-cost perfect matching via vertex potentials.
[^edmonds-blossom]: **Edmonds, J.** (1965), "Paths, trees, and flowers," _Canadian Journal of Mathematics_ 17, 449–467 — the blossom algorithm for maximum matching in general graphs.
[^kvv]: **Karp, R. M., Vazirani, U. V. & Vazirani, V. V.** (1990), "An optimal algorithm for on-line bipartite matching," _Proc. STOC 1990_, 352–358 — the RANKING algorithm and its $1 - 1/e$ competitive ratio.