Bipartite graphs — 2-coloring test, bipartite matching — Hopcroft-Karp: Worked examples

This page is a drill sheet. The parent topic note built the theory; here we walk every kind of input a problem can hand you and solve it fully. Before each answer, you forecast — guess the result, then check yourself.

The scenario matrix

Every question this topic throws at you is one of these cells:

#	Engine	Case class	What makes it tricky	Example
A	2-coloring	Even cycle	Should succeed — clean split	Ex 1
B	2-coloring	Odd cycle (triangle)	Must fail — the base non-bipartite shape	Ex 2
C	2-coloring	Odd cycle, length > 3 (pentagon)	Triangle-free but still fails	Ex 3
D	2-coloring	Disconnected graph	Must restart BFS per component	Ex 4
E	2-coloring	Degenerate: no edges / single vertex	Trivially bipartite	Ex 5
F	Matching	Greedy gets stuck → augmenting path needed	Greedy ≠ maximum	Ex 6
G	Matching	Hopcroft–Karp phase growth	Shortest path length strictly increases	Ex 7
H	Matching	König twist: min vertex cover / max independent set	Derive from matching	Ex 8
I	Word problem	Workers ↔ jobs assignment	Model then solve	Ex 9
J	Exam twist	"No triangle ⟹ bipartite?" trap	Spot the false claim	Ex 10

Cells A–E exhaust the coloring side (even, odd-small, odd-large, disconnected, degenerate). Cells F–H exhaust the matching side (the greedy trap, the phase mechanics, the König bonus). I and J are the real-world / exam wrappers. Nothing else can appear.

Example 1 — Cell A: an even cycle (square)

Forecast: even cycle → your gut should say bipartite, split into alternate corners.

Figure — Bipartite graphs — 2-coloring test, bipartite matching — Hopcroft-Karp

Set $color [1] = 0$ . Why this step? Every component needs one arbitrary seed; the rest is forced. Here $color$ is an array holding $0$ or $1$ (our two paints), or $- 1$ for "not yet painted".
Force neighbors of 1. Vertices $2$ and $4$ get $1 - 0 = 1$ . Why? The rule $color [v] = 1 - color [u]$ makes every edge cross between colors.
From 2, paint 3. $color [3] = 1 - 1 = 0$ . Why? Same forcing rule, one hop further.
Check the closing edge $(4, 3)$ . $color [4] = 1$ , $color [3] = 0$ — different, no clash. Why does it close cleanly? Look at the figure: walking the ring $0, 1, 0, 1$ returns to a $0$ -neighbor of the start. Length 4 is even, so colors line up.

Verify: Groups $L = {1, 3}$ (color 0), $R = {2, 4}$ (color 1). Every edge $1 - 2, 2 - 3, 3 - 4, 4 - 1$ crosses $L \leftrightarrow R$ . ✅ Bipartite.

Example 2 — Cell B: an odd cycle (triangle)

Forecast: triangle = smallest odd cycle → predict not bipartite.

$color [1] = 0$ . Why? Seed the component.
$color [2] = 1$ (forced opposite along edge $1 - 2$ ). Why? The deterministic rule.
$color [3] = 0$ (forced opposite along edge $2 - 3$ ). Why? One more hop, $1 - 1 = 0$ .
Check closing edge $(3, 1)$ . Both are $0$ → clash. Why must it clash? The cycle has 3 vertices; the pattern $0, 1, 0$ makes the last vertex the same color as the start, but they are joined by an edge. Odd length forces this collision.

Verify: An edge with equal endpoints ( $color [3] = color [1] = 0$ ) means no valid 2-coloring exists. ❌ Not bipartite — consistent with "odd cycle ⟹ not bipartite".

Example 3 — Cell C: an odd cycle longer than 3 (pentagon)

Forecast: many people say "no triangle → bipartite". Resist! It's an odd cycle. Predict not bipartite.

Paint around the ring: $color = [0, 1, 0, 1, 0]$ for vertices $1..5$ . Why? Keep forcing opposite along each edge.
Reach vertex 5: color $0$ . Why? It's the 5th vertex, an even number of hops (4) from vertex 1, so same color as vertex 1.
Check closing edge $(5, 1)$ . Both $0$ → clash. Why? Length 5 is odd; the alternating pattern cannot return consistently. The figure shows the "stuck" vertex glowing red where two 0's meet.

Verify: Clash exists → ❌ not bipartite, even though there is no triangle. This kills the myth in Cell J. Odd-cycle length here $= 5$ .

Example 4 — Cell D: a disconnected graph

Forecast: the answer for a disconnected graph is bipartite ⟺ every component is bipartite. Component $Q$ is a triangle → predict not bipartite.

BFS from 1 (color 0), color 2 = 1. Why? One component only reaches its own vertices; edge $1 - 2$ is fine.
BFS did NOT reach 3,4,5. Why restart? Vertices $3, 4, 5$ still have $color = - 1$ . The main loop must start a fresh BFS at the next uncolored vertex — this is the mistake the parent note warns about.
BFS from 3 (color 0) → 4 = 1 → 5 = 0. Closing edge $(5, 3)$ : both 0 → clash.

Verify: Component $P$ bipartite, component $Q$ not → whole graph ❌ not bipartite. Missing the restart would have wrongly reported "bipartite" after only seeing $P$ . Number of components touched $= 2$ .

Example 5 — Cell E: degenerate inputs

Forecast: with no edges there is no constraint to violate → predict both bipartite (vacuously).

Case (a): color the lone vertex 0. Why no clash possible? There are no edges, so the conflict test color[v]==color[u] is never evaluated.
Case (b): the main loop starts a BFS at each of the 5 uncolored isolated vertices, painting each 0. Why loop? Every vertex is its own component (Cell D logic applied to the extreme).
Put every vertex in $L$ , leave $R$ empty. Why allowed? The definition permits empty $R$ ; "every edge crosses" is vacuously true when $E = \emptyset$ .

Verify: No edge exists to break the rule → ✅ bipartite in both cases. Number of edges $= 0$ ; conflicts found $= 0$ .

Example 6 — Cell F: greedy gets stuck, augmenting path saves it

Forecast: greedy stopped at size 1. But you should sense a re-route via $a - y$ frees $x$ for $b$ → predict maximum size 2.

Current matching $M = {a - x}$ , size 1. Free vertices: $b$ (left), $y$ (right). Why stuck? $b$ 's only neighbor $x$ is already taken; greedy has no move.
Search an augmenting path from $b$ . Path $b free x matched a free y$ . Why this shape? An augmenting path alternates free, matched, free and ends at an unmatched right vertex ( $y$ ). It has length 3 (odd).
Flip every edge on the path. $b - x$ becomes matched, $a - x$ becomes free, $a - y$ becomes matched. Why flip? Flipping turns $k$ matched + $k + 1$ free into $k + 1$ matched — a net +1. See the figure's before/after.

Verify: New matching $M = {b - x, a - y}$ , size 2. Both $a, b$ matched, both $x, y$ matched — perfect. No unmatched-to-unmatched path remains, so by Berge's theorem it's maximum. Greedy $= 1 <$ maximum $= 2$ . See Berge's Theorem.

Example 7 — Cell G: Hopcroft–Karp phase mechanics

Forecast: Phase 1 finds length-1 paths; Phase 2 must go longer (length 3). Predict total matching 2 in two phases.

Phase 1 BFS. Free lefts $a, b$ at distance 0; each reaches a free right in one edge → shortest length 1. Why BFS? It measures the shortest alternating distance from all free lefts at once — the BFS layer number is exactly that distance.
Phase 1 DFS (maximal disjoint length-1 paths). Take $a \to x$ . Try $b$ : only neighbor $x$ already used this phase → no disjoint length-1 path for $b$ . Augment gives +1. Why stop at one? A phase uses only shortest, vertex-disjoint paths; $b$ 's path would reuse $x$ .
Phase 2 BFS. Only free left $b$ , free right $y$ . Shortest augmenting path now bounces through matched edge: $b \to x$ (free), $x \to a$ (matched), $a \to y$ (free) → length 3. Why longer? Exactly the Hopcroft–Karp guarantee: the shortest augmenting length strictly increases each phase.
Phase 2 DFS. Augment along $b - x - a - y$ → +1. Why terminate next? Phase 3 BFS finds no free left → no augmenting path → maximum.

Verify: Phase 1 length $= 1$ , Phase 2 length $= 3$ ( $1 < 3$ ✅ strictly increasing). Final matching size $= 2$ . Phases used $= 2 \leq 2 ∣ V ∣$ bound. See Maximum Flow for the flow view of the same augmentation.

Example 8 — Cell H: König's theorem twist

Forecast: König says these are pinned by the matching. Predict cover $= 3$ , independent set $= 10 - 3 = 7$ .

Min vertex cover. By König's Theorem, in a bipartite graph $min vertex cover = max matching = 3$ . Why? A vertex cover must touch every edge; König proves the tightest such set equals the matching size exactly in bipartite graphs.
Max independent set. Complement of a vertex cover: $max independent set = ∣ V ∣ - min vertex cover = 10 - 3 = 7$ . Why? Removing a minimum cover leaves the largest edge-free set.

Verify: cover $= 3$ , independent set $= 7$ , and $3 + 7 = 10 = ∣ V ∣$ ✅ (cover and independent set partition the vertices). Units: all counts of vertices.

Example 9 — Cell I: word problem (workers ↔ jobs)

Forecast: three workers, jobs $J_{1}, J_{2}, J_{3}$ all reachable → predict a perfect assignment of size 3.

Model as bipartite graph. $L = {W_{1}, W_{2}, W_{3}}$ , $R = {J_{1}, J_{2}, J_{3}}$ , edge = "can do". Why bipartite? Two kinds of things, edges only between kinds — the natural home of matching.
Assign forced ones first. $W_{2}$ has only $J_{1}$ → match $W_{2} - J_{1}$ . Why? A degree-1 vertex forces its single edge.
Now $W_{1}$ 's $J_{1}$ is taken, use $J_{2}$ . Match $W_{1} - J_{2}$ . Why? Its other option $J_{1}$ is gone.
$W_{3}$ 's $J_{2}$ taken, use $J_{3}$ . Match $W_{3} - J_{3}$ . Why? Remaining free job.

Verify: Matching ${W_{2} - J_{1}, W_{1} - J_{2}, W_{3} - J_{3}}$ , size 3 — every worker and every job used, no augmenting path remains. All 3 jobs staffed. ✅

Example 10 — Cell J: the exam trap

Forecast: you've already seen the pentagon. Predict False.

Recall the real criterion. Bipartite ⟺ no odd cycle (any odd length), not merely "no triangle". Why? Any odd cycle forces a coloring clash (Ex 2, Ex 3).
Produce a counterexample. The pentagon $C_{5}$ is connected, triangle-free, and (Ex 3) not bipartite. Why does it work? Its shortest odd cycle has length 5, so it dodges the triangle test yet still fails.

Verify: Counterexample exists → statement is False. Odd girth of $C_{5}$ $= 5$ , triangle count $= 0$ , bipartite $=$ false. ✅

Recall Quick self-check

Even cycle bipartite? ::: Yes — alternating colors close consistently. Smallest non-bipartite structure? ::: A triangle (odd cycle length 3). Triangle-free ⟹ bipartite? ::: No — any odd cycle (e.g. $C_{5}$ ) breaks it. Why loop over all vertices in the 2-coloring test? ::: Disconnected components each need their own BFS seed. Greedy matching size vs maximum? ::: Greedy can be smaller; augmenting paths reach the maximum. In Hopcroft–Karp, what strictly increases each phase? ::: The length of the shortest augmenting path. König in a bipartite graph relates which two quantities? ::: Max matching size $=$ min vertex cover size.