Bipartite Graphs and Matchings

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

A graph $G = (V, E)$ is bipartite if its vertex set partitions into two parts $X$ and $Y$ such that every edge has one endpoint in $X$ and one in $Y$ . A matching $M \subseteq E$ is a set of pairwise non-adjacent edges; intuitively, it pairs up vertices without overlap. Bipartite matching theory is central to combinatorial optimization because it admits efficient algorithms (unlike general matching, which is harder) and a beautiful duality: the size of a maximum matching equals the size of a minimum vertex cover. The surprising fact is that a purely existential question — "can we match everyone?" — reduces to a clean, checkable condition (Hall's condition) that fails the moment any subset of one side has too few neighbors.

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.

Formal Statement

Bipartite Graph

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

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

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

Characterization by Odd Cycles (König 1916)

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

G bipartite ⟺ \forall cycles C \subseteq G : ∣ C ∣ \equiv 0 (mod 2) .

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

Matching, Maximum, Perfect

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

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

⟳"share no endpoint" is just disjointness of the two-element edge sets.

$M$ is maximum if no matching has more edges: $∣ M ∣ = ν (G)$ , where $ν (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.

Vertex Cover and Covering Number

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

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

⟳a cover must "hit" each edge, so at least one endpoint lies in

U

The minimum size of a vertex cover is $τ (G)$ .

Hall'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$ ,

∣ N (S) ∣ \geq ∣ S ∣,

where

N (S) = {y \in Y : \exists x \in S, {x, y} \in E}

is the neighborhood of

S

⟳necessity is counting; sufficiency follows by augmenting-path induction or by reducing to König's theorem.

König's Theorem (1931)

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

ν (G) = τ (G) .

⟳build a vertex cover of size

ν (G)

from an alternating-path reachability argument; weak duality gives

ν \leq τ

always.

Deficiency Version (König–Ore)

The maximum matching size obeys the deficiency formula:

ν (G) = ∣ X ∣ - S \subseteq X max (∣ S ∣ - ∣ N (S) ∣) .

⟳the term

max (∣ S ∣ - ∣ N (S) ∣)

measures the worst Hall-violating set; subtract this "deficiency" from

∣ X ∣

Why It Holds / Derivation

Hall's Theorem via Augmenting Paths

We prove the nontrivial direction: if $∣ N (S) ∣ \geq ∣ 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

Y

) and matching (from

Y

back to

X

). Let

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

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

y

, contradicting maximality of

M

), and its match lies in

S

. Hence

M

gives a bijection between

T

and

S ∖ {x_{0}}

, so

∣ T ∣ = ∣ S ∣ - 1.

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

■

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

C = (X ∖ Z) \cup (Y \cap Z) .

⟳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 \in / Z

, then

x \in C

. So every edge is covered. Claim 2 — $∣ C ∣ = ∣ M ∣$ . No edge of

M

connects

X ∖ Z

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 ∣ = ν (G)

Since $τ \geq ν$ always (each matching edge needs its own cover vertex) and we exhibited a cover of size $ν$ , we get $τ = ν$ . $■$

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.

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

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

<svg viewBox="0 0 460 300" xmlns="http://www.w3.org/2000/svg">
<rect width="460" height="300" fill="#0a0e17"/>
<text x="70" y="30" fill="#e2e8f0" font-size="15" font-family="sans-serif">X</text>
<text x="370" y="30" fill="#e2e8f0" font-size="15" font-family="sans-serif">Y</text>
<!-- X vertices -->
<circle cx="80" cy="70" r="9" fill="#0a0e17" stroke="#94a3b8" stroke-width="2"/>
<circle cx="80" cy="150" r="9" fill="#0a0e17" stroke="#94a3b8" stroke-width="2"/>
<circle cx="80" cy="230" r="9" fill="#0a0e17" stroke="#94a3b8" stroke-width="2"/>
<!-- Y vertices -->
<circle cx="380" cy="70" r="9" fill="#0a0e17" stroke="#94a3b8" stroke-width="2"/>
<circle cx="380" cy="150" r="9" fill="#0a0e17" stroke="#94a3b8" stroke-width="2"/>
<circle cx="380" cy="230" r="9" fill="#0a0e17" stroke="#94a3b8" stroke-width="2"/>
<text x="55" y="75" fill="#e2e8f0" font-size="13" font-family="sans-serif">x1</text>
<text x="55" y="155" fill="#e2e8f0" font-size="13" font-family="sans-serif">x2</text>
<text x="55" y="235" fill="#e2e8f0" font-size="13" font-family="sans-serif">x3</text>
<text x="395" y="75" fill="#e2e8f0" font-size="13" font-family="sans-serif">y1</text>
<text x="395" y="155" fill="#e2e8f0" font-size="13" font-family="sans-serif">y2</text>
<text x="395" y="235" fill="#e2e8f0" font-size="13" font-family="sans-serif">y3</text>
<!-- non-matching edges -->
<line x1="89" y1="73" x2="371" y2="147" stroke="#94a3b8" stroke-width="1.5" stroke-dasharray="5,4"/>
<line x1="89" y1="153" x2="371" y2="227" stroke="#94a3b8" stroke-width="1.5" stroke-dasharray="5,4"/>
<line x1="89" y1="230" x2="371" y2="73" stroke="#94a3b8" stroke-width="1"/>
<!-- matching edges (gold) -->
<line x1="89" y1="150" x2="371" y2="150" stroke="#d4a853" stroke-width="3"/>
<line x1="89" y1="230" x2="371" y2="230" stroke="#d4a853" stroke-width="3"/>
<text x="150" y="285" fill="#d4a853" font-size="12" font-family="sans-serif">gold = matched, dashed = unmatched path edges</text>
<!-- augmenting path label -->
<text x="120" y="55" fill="#e2e8f0" font-size="11" font-family="sans-serif">x1 free → y2 → x2 → y3 → x3 free</text>
</svg>

Worked Examples

Checking 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 \geq 1

∣ N ({b}) ∣ = 1 \geq 1

. 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]:

ν = ∣ X ∣ - def = 3 - 1 = 2.

Answer:

ν = 2 (no perfect matching; one job unfillable)

Verifying König Duality

Given: Bipartite graph

X = {x_{1}, x_{2}}

Y = {y_{1}, y_{2}}

with edges

x_{1} y_{1}, x_{1} y_{2}, x_{2} y_{1}

(a "path-plus" shape). Step 1 — Find a maximum matching. Take

M = {x_{1} y_{2}, x_{2} y_{1}}

. Both

X

-vertices saturated;

∣ M ∣ = 2

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

ν = 2

. Step 3 — Find a minimum vertex cover.

C = {x_{1}, y_{1}}

: edge

x_{1} y_{1}

hit by

x_{1}

x_{1} y_{2}

x_{1}

x_{2} y_{1}

y_{1}

. Size

2

. No single vertex covers all 3 edges, so

τ = 2

. Step 4 — Confirm [6].

ν = τ = 2

. ✓ Answer:

ν = τ = 2, perfect matching exists

Common Misconceptions

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 (

ν = τ

) holds only for bipartite graphs. In general graphs

ν \leq τ \leq 2 ν

, and the gap can be real. König fails in general graphs. Take the triangle

K_{3}

(odd cycle, not bipartite). Maximum matching has

ν = 1

(one edge; the third vertex is left out). But minimum vertex cover needs

τ = 2

vertices, since one vertex leaves an uncovered edge. Here

ν = 1 \neq = 2 = τ

, so duality breaks precisely because

K_{3}

has an odd cycle.

Connections

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.

Real-World Applications

Job/task assignment: matching workers to tasks they are qualified for (Hungarian algorithm in operations research).
Scheduling and timetabling: assigning courses to rooms/time-slots without conflicts via edge colorings of bipartite graphs (König's edge-coloring theorem: $χ^{'} = Δ$ ).
Network routing & switch scheduling: input-output crossbar switches in routers use bipartite matching (e.g., iSLIP algorithm) to pair input ports with output ports each cycle.
Kidney exchange / organ matching: donor–recipient compatibility modeled as matching problems.
Online advertising: matching ad impressions to advertisers (online bipartite matching, RANKING algorithm) under arriving requests.
Image and graph correspondence: matching feature points between two images (computer vision) as a weighted bipartite assignment.
Resource allocation / stable marriage: the Gale–Shapley algorithm produces stable matchings for college admissions and medical residency placement (NRMP).

Historical Development

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 $ν = τ$ 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 (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$ ).

Subtleties & Limits

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.