Bipartite graphs — 2-coloring test, bipartite matching — Hopcroft-Karp: Visual walkthrough

Step 1 — A graph is just dots and lines

WHAT. Before any theorem, fix the vocabulary. A graph is a bag of dots (we call them vertices) and lines joining some pairs of dots (we call them edges). Nothing more.

WHY. Every symbol later leans on this. When I write $G = (V, E)$ I mean: $G$ is the whole picture, $V$ is the set of dots, $E$ is the set of lines. Read $(u, v) \in E$ as "there is a line between dot $u$ and dot $v$ ."

$V$ ::: the set of all dots (vertices)
$E$ ::: the set of all lines (edges), each edge joins two dots
$(u, v) \in E$ ::: " $u$ and $v$ are connected by a line"

PICTURE. Four dots, some lines. The dots are named; the lines are just plain connections — no direction, no weight yet.

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

Step 2 — Paint the dots with two colors

WHAT. Now play a game. You have exactly two paint pots — call them color $0$ and color $1$ . Rule of the game: no line may join two dots of the same color.

WHY. This is the whole definition of bipartite, dressed as a game. If you can win (paint everything legally), the two colors carve the dots into two teams: $L = {dots painted 0}, R = {dots painted 1}$

$L$ ::: the "left" team — all dots you painted color $0$
$R$ ::: the "right" team — all dots you painted color $1$

Every line then runs between $L$ and $R$ , never inside a team — that is exactly what the definition demanded. (This is the same idea as Graph Coloring, but frozen at two colors.)

PICTURE. The same four dots from Step 1, now legally painted. Notice each burnt-orange line has one plum end and one teal end.

Step 3 — Following a line forces the color

WHAT. With only two paint pots, the moment one dot is painted, its neighbor has no choice. If $u$ is color $0$ , its neighbor $v$ must be color $1$ , because same-color-across-a-line is forbidden.

WHY. Two colors means "not equal to $u$ 's color" has exactly one answer. We write it as arithmetic: $color [v] = the two paints 1 - the color we already fixed color [u]$

$color [u]$ ::: the color already chosen for dot $u$ , a value in ${0, 1}$
$1 - color [u]$ ::: flips $0 \to 1$ and $1 \to 0$ — "the other paint"

Why subtraction? Because $1 - 0 = 1$ and $1 - 1 = 0$ : one tidy formula that always hands back the opposite color. No if needed.

Once you fix the very first dot, this rule spreads outward like dominoes — every dot in a connected chunk gets forced. That is why a connected piece has only two legal colorings (the one you found, and its swap).

PICTURE. A short chain $u - v - w$ . Fix $u = 0$ ; the arrow shows $v$ forced to $1$ , then $w$ forced back to $0$ .

Step 4 — Walk a cycle: even survives, odd explodes

WHAT. A cycle is a loop of lines that returns to where it started. March around it applying the forcing rule: $0, 1, 0, 1, \dots$

WHY. The colors alternate. To come home to the starting dot with the color it already has, you must have taken an even number of steps.

Loop of 4 dots (a square): $0 \to 1 \to 0 \to 1 \to$ back to the $0$ -dot. ✅ consistent.
Loop of 3 dots (a triangle): $0 \to 1 \to 0 \to$ back to the start... but the start is $0$ and this last line demands it be $1$ . Clash. ❌

An odd loop forces the start dot to be both colors at once. Impossible. That is the theorem in one breath: $odd cycle present ⟺ cannot 2-color ⟺ not bipartite .$

PICTURE. Left: the square closes cleanly. Right: the triangle's last line lights up red — the closing dot is asked to be $0$ and $1$ simultaneously.

Step 5 — The test is just this rule + BFS

WHAT. To decide bipartiteness, paint the start dot $0$ , then use a wave (BFS) or a deep dive (DFS) to push the forced color outward. If two same-colored dots ever share a line — clash, stop, "not bipartite."

WHY. BFS visits dots layer by layer, so consecutive layers automatically get alternating colors. We never choose; we only check. A clash is precisely the moment an odd cycle closes.

$dist [v]$ ::: how many lines from the start dot $s$ to $v$ in the BFS wave
$color [v] = dist [v] mod 2$ ::: even distance → color $0$ , odd → color $1$

$mod 2$ means "remainder after dividing by 2" — it is the alternation. Loop over every uncolored dot to also catch separate islands (disconnected components).

PICTURE. BFS layers spreading from $s$ ; each ring alternates color. One back-edge inside the same ring would signal the clash.

Step 6 — A matching, and the path that grows it

WHAT. A matching $M$ is a set of chosen edges so that no dot is used twice — like pairing dancers, everyone in at most one pair. An augmenting path starts and ends at unpaired dots and strictly alternates: free line, matched line, free line, …, free line.

WHY. An augmenting path always has one more free edge than matched edge. If we swap every edge on it — free becomes matched, matched becomes free — we gain exactly: $(k + 1) new matches - k lost matches = + 1.$

$k$ ::: number of matched edges on the path (the middle ones)
$k + 1$ ::: number of free edges on the path (the ones we turn ON)
endpoints ::: were unpaired, now become paired

The two endpoints were lonely and are now paired; every interior dot stays paired. Net effect: the matching grows by one. This is exactly Berge's Theorem: a matching is maximum precisely when no augmenting path exists — because as long as one exists, you can always do this $+ 1$ flip.

PICTURE. A path $b - x = a - y$ where $=$ is the one matched edge; below it, the same path after the flip: two matched edges, one freed.

Step 7 — Hopcroft–Karp: many shortest paths at once

WHAT. Kuhn's method finds one augmenting path at a time. Maximum Flow-flavoured Hopcroft–Karp instead grabs a whole maximal set of shortest, dot-disjoint augmenting paths in one phase, then flips them all together.

WHY. Each phase forces the shortest augmenting path to get strictly longer next time. After about $V$ phases the paths are so long that only $O (V)$ remain — giving the famous bound: $O (E V)$

$V$ ::: number of dots — $V$ bounds the number of phases
$E$ ::: number of lines — cost of one BFS+DFS sweep per phase
one phase ::: BFS to layer the graph, then DFS to extract disjoint shortest paths

PICTURE. Two-phase story. Phase 1: two length-1 paths, only one usable disjointly ( $a - x$ ). Phase 2: the shortest path is now length 3, $b - x = a - y$ , and flipping it reaches a perfect matching. The path grew from 1 to 3 — the Hopcroft–Karp guarantee.

The one-picture summary

Recall Retell the whole walkthrough in plain words (Feynman check)

A graph is just dots and lines. Try to paint the dots with two colors so no line joins same colors. With only two paints, painting one dot forces its neighbours to the opposite — a domino rule $color [v] = 1 - color [u]$ . Walk around a loop and the colors alternate $0, 1, 0, 1$ ; to arrive home consistently the loop must be even. An odd loop asks the start dot to be both colors — impossible — so odd cycle = not bipartite. That's the whole 2-coloring test: paint the start, spread with BFS, and shout "not bipartite" the instant two same-colored dots share a line. For matching (pairing left dots to right dots, each used once), the magic move is the augmenting path: a zig-zag of free/matched edges from one lonely dot to another. Flip every edge on it and you gain exactly one pair. When no such path is left, you're maximum (Berge). Hopcroft–Karp just flips many shortest disjoint paths per round, and since the shortest path length keeps rising, only $V$ rounds are needed — total $O (E V)$ .