Bipartite Matching

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 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

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.

bipartite_graph.pypython

from collections.abc import Hashable
from typing import Generic, TypeVar

Label = TypeVar("Label", bound=Hashable)

class BipartiteVertex(Generic[Label]):
  """
    One vertex of a bipartite graph: its label and which side it sits on.\n
    `is_left` is True for an L-vertex, False for an R-vertex. A left vertex\n
    records its right-side neighbors in `neighbors`; right vertices keep the\n
    mirror list so either side can be iterated.\n
  """

  def __init__(self, label: Label, is_left: bool) -> None:
    self.label: Label = label
    self.is_left: bool = is_left
    self.neighbors: list[BipartiteVertex[Label]] = []

  def __repr__(self) -> str:
    side: str = "L" if self.is_left else "R"
    return f"BipartiteVertex({self.label!r}, {side})"

class BipartiteGraph(Generic[Label]):
  """
    A bipartite graph over a left side L and a right side R.\n
    Add vertices with `add_left` / `add_right` (or let `add_edge` create them)\n
    and connect a left label to a right label with `add_edge`. The two sides\n
    are stored in separate label maps, so the same label may appear once on\n
    each side.\n
  """

  def __init__(self) -> None:
    self._left: dict[Label, BipartiteVertex[Label]] = {}
    self._right: dict[Label, BipartiteVertex[Label]] = {}

  def add_left(self, label: Label) -> BipartiteVertex[Label]:
    """
      Return the left vertex for `label`, creating it if absent.\n
    """
    vertex = self._left.get(label)
    if vertex is None:
      vertex = BipartiteVertex(label, is_left=True)
      self._left[label] = vertex
    return vertex

  def add_right(self, label: Label) -> BipartiteVertex[Label]:
    """
      Return the right vertex for `label`, creating it if absent.\n
    """
    vertex = self._right.get(label)
    if vertex is None:
      vertex = BipartiteVertex(label, is_left=False)
      self._right[label] = vertex
    return vertex

  def add_edge(self, left_label: Label, right_label: Label) -> None:
    """
      Connect a left label to a right label, creating either vertex as\n
      needed. Duplicate edges are ignored so adjacency lists stay simple.\n
    """
    left_vertex: BipartiteVertex[Label] = self.add_left(left_label)
    right_vertex: BipartiteVertex[Label] = self.add_right(right_label)
    if right_vertex not in left_vertex.neighbors:
      left_vertex.neighbors.append(right_vertex)
      right_vertex.neighbors.append(left_vertex)

  def left_vertex(self, label: Label) -> BipartiteVertex[Label]:
    """
      The left vertex carrying `label` (raises KeyError if absent).\n
    """
    return self._left[label]

  def right_vertex(self, label: Label) -> BipartiteVertex[Label]:
    """
      The right vertex carrying `label` (raises KeyError if absent).\n
    """
    return self._right[label]

  @property
  def left_vertices(self) -> list[BipartiteVertex[Label]]:
    """
      Every left vertex, in insertion order.\n
    """
    return list(self._left.values())

  @property
  def right_vertices(self) -> list[BipartiteVertex[Label]]:
    """
      Every right vertex, in insertion order.\n
    """
    return list(self._right.values())

  @property
  def left_labels(self) -> list[Label]:
    """
      Every left label, in insertion order.\n
    """
    return list(self._left)

  @property
  def right_labels(self) -> list[Label]:
    """
      Every right label, in insertion order.\n
    """
    return list(self._right)

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).

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.

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.

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).

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

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_{1} r_{1}, L_{1} r_{2}, L_{2} r_{1}, L_{3} r_{2}, L_{3} r_{3}, L_{4} r_{3}, L_{4} r_{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_{1} r_{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.

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}

r_{2}

L_{2}

can take

r_{1}

. Free vertices are blue-outlined; gray edges are unmatched.

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.¹

Algorithm 1:

\textsc{Kuhn}(G, L, R)

— maximum bipartite matching by augmenting paths

1
foreach $v \in R$ do $\text{match}[v] \gets \textsc{nil}$
who $v$ is matched to
2
$\text{size} \gets 0$
3
foreach $u \in L$ do
4
reset $\text{seen}[\,\cdot\,] \gets \textsc{false}$ for all $v \in R$
5
if $\textsc{TryKuhn}(u)$ then $\text{size} \gets \text{size} + 1$
6
return $\text{size}$
and $\text{match}[\cdot]$ holds the matching
7
8
// try to match (or re-route) $u$ along an alternating path
9
function $\textsc{TryKuhn}(u)$ :
10
foreach $v \in \text{adj}(u)$ do
11
if not $\text{seen}[v]$ then
12
$\text{seen}[v] \gets \textsc{true}$
13
// $v$ free, or its partner can step aside
14
if $\text{match}[v] = \textsc{nil}$ or $\textsc{TryKuhn}(\text{match}[v])$ then
15
$\text{match}[v] \gets u$
16
return $\textsc{true}$
17
return $\textsc{false}$

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}

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 (V E)$ can be $O (V^{3})$ , which is why the next algorithm matters.

kuhn_matching.pypython

from collections.abc import Hashable
from typing import Generic, Optional, TypeVar

from bipartite_graph import BipartiteGraph, BipartiteVertex

Label = TypeVar("Label", bound=Hashable)

class Matching(Generic[Label]):
  """
    A matching in a bipartite graph, paired off in both directions.\n
    `partner_of_left[left_label]` is the right label it is matched to (absent\n
    if free), and `partner_of_right[right_label]` is the mirror map. The graph\n
    is kept so structural queries (Konig's vertex cover) can reuse it.\n
  """

  def __init__(self, graph: BipartiteGraph[Label]) -> None:
    self.graph: BipartiteGraph[Label] = graph
    self.partner_of_left: dict[Label, Label] = {}
    self.partner_of_right: dict[Label, Label] = {}

  def pair(self, left_label: Label, right_label: Label) -> None:
    """
      Record `left_label`-`right_label` as a matched edge, both ways.\n
    """
    self.partner_of_left[left_label] = right_label
    self.partner_of_right[right_label] = left_label

  @property
  def size(self) -> int:
    """
      The number of matched edges.\n
    """
    return len(self.partner_of_left)

  def edges(self) -> list[tuple[Label, Label]]:
    """
      The matched edges as (left_label, right_label) pairs, left order.\n
    """
    return list(self.partner_of_left.items())

def kuhn_matching(graph: BipartiteGraph[Label]) -> Matching[Label]:
  """
    A maximum matching of `graph` by Kuhn's augmenting-path search.\n
  """
  matching: Matching[Label] = Matching(graph)

  def try_augment(
    left_vertex: BipartiteVertex[Label],
    seen: set[Label],
  ) -> bool:
    """
      Search for an augmenting path out of `left_vertex`, flipping it on\n
      success. `seen` holds the right labels already explored this attempt.\n
    """
    for right_vertex in left_vertex.neighbors:
      right_label: Label = right_vertex.label
      if right_label in seen:
        continue
      seen.add(right_label)

      # the right vertex is free, or its partner can step aside for us.
      current_partner: Optional[Label] = matching.partner_of_right.get(
        right_label
      )
      if current_partner is None or try_augment(
        graph.left_vertex(current_partner), seen
      ):
        matching.pair(left_vertex.label, right_label)
        return True
    return False

  # grow the matching by one augmenting search per left vertex.
  for left_vertex in graph.left_vertices:
    seen: set[Label] = set()
    try_augment(left_vertex, seen)

  return 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.²

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 2:

\textsc{HopcroftKarp}(G, L, R)

— shortest augmenting paths in phases

1
foreach $u \in L$ do $\text{matchL}[u] \gets \textsc{nil}$
2
foreach $v \in R$ do $\text{matchR}[v] \gets \textsc{nil}$
3
$\text{size} \gets 0$
4
while $\textsc{Bfs}()$ finds at least one augmenting path do
one phase
5
foreach free $u \in L$ do
6
if $\textsc{Dfs}(u)$ then $\text{size} \gets \text{size} + 1$
7
return $\text{size}$
8
9
// layer by alternating distance; return true if a free right vertex is reached
10
function $\textsc{Bfs}()$ :
11
$Q \gets$ empty queue
12
foreach $u \in L$ do
13
if $\text{matchL}[u] = \textsc{nil}$ then $\text{dist}[u] \gets 0$ ; enqueue $u$
14
else $\text{dist}[u] \gets \infty$
15
$\text{found} \gets \textsc{false}$
16
while $Q$ nonempty do
17
$u \gets$ dequeue
18
foreach $v \in \text{adj}(u)$ do
19
$w \gets \text{matchR}[v]$
left vertex across the matched edge
20
if $w = \textsc{nil}$ then $\text{found} \gets \textsc{true}$
reached a free right vertex
21
else if $\text{dist}[w] = \infty$ then $\text{dist}[w] \gets \text{dist}[u] + 1$ ; enqueue $w$
22
return $\text{found}$
23
24
// extend one shortest augmenting path from $u$ , respecting BFS layers
25
function $\textsc{Dfs}(u)$ :
26
foreach $v \in \text{adj}(u)$ do
27
$w \gets \text{matchR}[v]$
28
if $w = \textsc{nil}$ or ( $\text{dist}[w] = \text{dist}[u] + 1$ and $\textsc{Dfs}(w)$ ) then
29
$\text{matchL}[u] \gets v$ ; $\text{matchR}[v] \gets u$
flip this edge
30
return $\textsc{true}$
31
$\text{dist}[u] \gets \infty$
dead end; never revisit
32
return $\textsc{false}$

For dense bipartite graphs this is a real gain over Kuhn's $O (V E)$ , 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 V)$ bound is Dinic's on such networks.

hopcroft_karp.pypython

from collections import deque
from collections.abc import Hashable
from math import inf
from typing import Optional, TypeVar

from bipartite_graph import BipartiteGraph, BipartiteVertex
from kuhn_matching import Matching

Label = TypeVar("Label", bound=Hashable)

def hopcroft_karp(graph: BipartiteGraph[Label]) -> Matching[Label]:
  """
    A maximum matching of `graph` by shortest augmenting paths in phases.\n
  """
  matching: Matching[Label] = Matching(graph)

  # alternating distance to each left vertex within the current phase;
  # inf means unreached, so it cannot start a path this phase.
  distance: dict[Label, float] = {}

  def build_layers() -> bool:
    """
      BFS from every free left vertex, layering left vertices by alternating\n
      distance. Returns True if some augmenting path (a free right vertex)\n
      is reachable, meaning the phase has work to do.\n
    """
    # free left vertices start at distance 0; matched ones start unreached.
    queue: deque[BipartiteVertex[Label]] = deque()
    for left_vertex in graph.left_vertices:
      if left_vertex.label not in matching.partner_of_left:
        distance[left_vertex.label] = 0
        queue.append(left_vertex)
      else:
        distance[left_vertex.label] = inf

    # walk the layers, recording the first free right vertex reached.
    found: bool = False
    while queue:
      left_vertex = queue.popleft()
      for right_vertex in left_vertex.neighbors:
        across: Optional[Label] = matching.partner_of_right.get(
          right_vertex.label
        )
        if across is None:
          # a free right vertex: an augmenting path ends here.
          found = True
        elif distance[across] == inf:
          distance[across] = distance[left_vertex.label] + 1
          queue.append(graph.left_vertex(across))
    return found

  def extend_path(left_vertex: BipartiteVertex[Label]) -> bool:
    """
      DFS one shortest augmenting path out of `left_vertex`, respecting the\n
      BFS layers, and flip its edges on success.\n
    """
    for right_vertex in left_vertex.neighbors:
      across: Optional[Label] = matching.partner_of_right.get(
        right_vertex.label
      )
      reaches_free: bool = across is None
      steps_forward: bool = (
        across is not None
        and distance[across] == distance[left_vertex.label] + 1
        and extend_path(graph.left_vertex(across))
      )
      if reaches_free or steps_forward:
        matching.pair(left_vertex.label, right_vertex.label)
        return True

    # dead end: bar this vertex from the rest of the phase.
    distance[left_vertex.label] = inf
    return False

  # each phase: layer, then flip every disjoint shortest path found.
  while build_layers():
    for left_vertex in graph.left_vertices:
      if left_vertex.label not in matching.partner_of_left:
        extend_path(left_vertex)

  return matching

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.³

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 ∣ \geq ∣ M ∣$ always — this is weak duality, exactly as $∣ f ∣ \leq c (S, T)$ was for flow. König's theorem says that in bipartite graphs the bound is tight.

Proof. Weak duality gives $max ∣ M ∣ \leq 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 ∖ Z) \cup (R \cap Z) .

$C$ is a vertex cover. Suppose some edge $(ℓ, r)$ , $ℓ \in L$ , $r \in R$ , is covered by neither: $ℓ \in Z$ and $r \in / Z$ . Since $ℓ \in Z$ is reachable by an alternating path, extending it by the unmatched-or-matched edge $ℓ r$ would put $r \in Z$ too — unless $ℓ r \in M$ , but then $r$ is reached from $ℓ$ 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 $ℓ \in L ∖ 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 ∖ Z$ to $R \cap Z$ : if $ℓ r \in M$ with $r \in Z$ , the alternating path to $r$ leaves along its matched edge to $ℓ$ , putting $ℓ \in Z$ . Hence each cover vertex is the endpoint of a distinct matching edge, giving $∣ C ∣ \leq ∣ M ∣$ , and with weak duality $∣ C ∣ = ∣ M ∣$ . $□$

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 ∖ C$ is a maximum independent set, also polynomial here.

konig_vertex_cover.pypython

from collections import deque
from collections.abc import Hashable
from typing import Generic, Optional, TypeVar

from bipartite_graph import BipartiteGraph, BipartiteVertex
from kuhn_matching import Matching, kuhn_matching

Label = TypeVar("Label", bound=Hashable)

class Cover(Generic[Label]):
  """
    A minimum vertex cover of a bipartite graph, split by side.\n
    `left` and `right` hold the cover labels on each side; `independent_set`\n
    is the complement, a maximum independent set. By Konig's theorem the total\n
    cover size equals the maximum matching size.\n
  """

  def __init__(
    self,
    left: set[Label],
    right: set[Label],
    independent_left: set[Label],
    independent_right: set[Label],
  ) -> None:
    self.left: set[Label] = left
    self.right: set[Label] = right
    self.independent_left: set[Label] = independent_left
    self.independent_right: set[Label] = independent_right

  @property
  def size(self) -> int:
    """
      The number of vertices in the cover.\n
    """
    return len(self.left) + len(self.right)

  def covers(self, left_label: Label, right_label: Label) -> bool:
    """
      Whether the edge (left_label, right_label) has a cover endpoint.\n
    """
    return left_label in self.left or right_label in self.right

def _alternating_reachable(
  graph: BipartiteGraph[Label],
  matching: Matching[Label],
) -> tuple[set[Label], set[Label]]:
  """
    The set Z of vertices reachable from the free left vertices by alternating\n
    paths, returned as (reachable left labels, reachable right labels).\n
    Starting free and unmatched-first, a left vertex steps to a right neighbor\n
    along an unmatched edge, and a reached right vertex steps back to its\n
    partner along the matched edge.\n
  """
  reachable_left: set[Label] = set()
  reachable_right: set[Label] = set()
  queue: deque[BipartiteVertex[Label]] = deque()

  # seed the search at the free (unmatched) left vertices.
  for left_vertex in graph.left_vertices:
    if left_vertex.label not in matching.partner_of_left:
      reachable_left.add(left_vertex.label)
      queue.append(left_vertex)

  while queue:
    left_vertex = queue.popleft()
    partner: Optional[Label] = matching.partner_of_left.get(left_vertex.label)

    for right_vertex in left_vertex.neighbors:
      # cross only unmatched edges, and only to fresh right vertices.
      if right_vertex.label == partner:
        continue
      if right_vertex.label in reachable_right:
        continue
      reachable_right.add(right_vertex.label)

      # then step back along the matched edge, if any.
      next_left: Optional[Label] = matching.partner_of_right.get(
        right_vertex.label
      )
      if next_left is not None and next_left not in reachable_left:
        reachable_left.add(next_left)
        queue.append(graph.left_vertex(next_left))

  return reachable_left, reachable_right

def minimum_vertex_cover(graph: BipartiteGraph[Label]) -> Cover[Label]:
  """
    A minimum vertex cover of `graph`, with its complementary maximum\n
    independent set, built from a maximum matching via Konig's construction.\n
  """
  matching: Matching[Label] = kuhn_matching(graph)
  reachable_left, reachable_right = _alternating_reachable(graph, matching)

  all_left: set[Label] = set(graph.left_labels)
  all_right: set[Label] = set(graph.right_labels)

  # C = (L \ Z) union (R intersect Z).
  cover_left: set[Label] = all_left - reachable_left
  cover_right: set[Label] = all_right & reachable_right

  # the complement on each side is the maximum independent set.
  independent_left: set[Label] = all_left - cover_left
  independent_right: set[Label] = all_right - cover_right

  return Cover(cover_left, cover_right, independent_left, independent_right)

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.

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$ ).

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

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:

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.

hall_condition.pypython

from collections.abc import Hashable
from itertools import combinations
from typing import Optional, TypeVar

from bipartite_graph import BipartiteGraph
from kuhn_matching import kuhn_matching
from konig_vertex_cover import minimum_vertex_cover

Label = TypeVar("Label", bound=Hashable)

def neighbors_of(
  graph: BipartiteGraph[Label],
  left_labels: set[Label],
) -> set[Label]:
  """
    N(S): the right labels adjacent to some vertex of `left_labels`.\n
  """
  # union the right neighbors over every chosen left vertex.
  result: set[Label] = set()
  for left_label in left_labels:
    for right_vertex in graph.left_vertex(left_label).neighbors:
      result.add(right_vertex.label)

  return result

def saturates_left(graph: BipartiteGraph[Label]) -> bool:
  """
    Whether some matching saturates every left vertex of `graph`.\n
    Decided by a maximum matching: L is saturable iff the matching size\n
    reaches |L|. This is the efficient face of Hall's theorem.\n
  """
  return kuhn_matching(graph).size == len(graph.left_labels)

def hall_violator(graph: BipartiteGraph[Label]) -> Optional[set[Label]]:
  """
    A witness set S subset of L with |N(S)| < |S| if the marriage condition\n
    fails, else None. The witness is built from Konig's minimum vertex cover:\n
    when L is not saturable the cover has size < |L|, and S = L \\ C_L\n
    violates Hall's condition, since every neighbor of S lies in C_R.\n
  """
  cover = minimum_vertex_cover(graph)
  if cover.size == len(graph.left_labels):
    return None

  # S = L \ C_L; its neighborhood is contained in C_R, which is smaller.
  witness: set[Label] = set(graph.left_labels) - cover.left
  return witness

def hall_violator_brute_force(
  graph: BipartiteGraph[Label],
) -> Optional[set[Label]]:
  """
    The same witness by exhaustive subset search — the reference for tests.\n
    Returns any S subset of L with |N(S)| < |S|, or None if none exists.\n
  """
  left_labels: list[Label] = graph.left_labels
  for size in range(1, len(left_labels) + 1):
    for chosen in combinations(left_labels, size):
      subset: set[Label] = set(chosen)
      if len(neighbors_of(graph, subset)) < len(subset):
        return subset
  return None

def is_regular(graph: BipartiteGraph[Label]) -> Optional[int]:
  """
    The common degree `d` if `graph` is d-regular (both sides, every vertex\n
    of degree d) and non-empty, else None. A d-regular bipartite graph with\n
    d >= 1 always has a perfect matching, by Hall's corollary.\n
  """
  # collect every vertex degree across both sides.
  degrees: set[int] = set()
  for left_vertex in graph.left_vertices:
    degrees.add(len(left_vertex.neighbors))
  for right_vertex in graph.right_vertices:
    degrees.add(len(right_vertex.neighbors))

  # regular iff a single shared degree, and that degree is nonzero.
  if len(degrees) != 1:
    return None
  degree: int = next(iter(degrees))
  return degree if degree != 0 else None

The reduction to max-flow

The combinatorial view and the flow view describe the same object. The max-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 $ℓ \in L$ , an edge $s \to ℓ$ of capacity $1$ ;
for each original edge $ℓ r \in E$ , a directed edge $ℓ \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 ℓ$ lets at most one middle edge out of $ℓ$ 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.

Bipartite matching as unit-capacity max-flow. Source

s

feeds each left vertex (capacity

1

), original edges point

L

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

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 $ℓ \to r$ is an unmatched edge, a backward $r \to ℓ$ 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 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})$ .⁴ 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.⁵ Micali and Vazirani later pushed general matching to $O (E V)$ , matching the bipartite bound.

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.

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.⁶ 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 (V E)$ ; Hopcroft–Karp batches shortest, disjoint augmenting paths per phase for $O (E 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) ∣ \geq ∣ S ∣$ for all $S \subseteq L$ ; it yields perfect matchings for $d$ -regular bipartite graphs and is König's dual face.

CLRS, Ch. 26 — Maximum Flow: bipartite matching as unit-capacity flow, and the augmenting-path method underlying Kuhn's algorithm. ↩
Erickson, Ch. 11 — Applications of Maximum Flow: matching, vertex cover, and the shortest-augmenting-path speedup behind Hopcroft–Karp / Dinic. ↩
Skiena, §6 — Weighted Graph Algorithms: bipartite matching in practice, and the matching / vertex-cover duality (König). ↩
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, J. (1965), Paths, trees, and flowers, Canadian Journal of Mathematics 17, 449–467 — the blossom algorithm for maximum matching in general graphs. ↩
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. ↩