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

The colouring rule. We label each vertex with one of two colours, written $0$ and $1$. These are just two arbitrary names for the two colour classes (call them "black/white" if you prefer) — the numbers carry no arithmetic meaning beyond "different from each other." The rule is: fix one start vertex's colour, then every neighbour is forced to the opposite colour via $\text{colour}[v]=1-\text{colour}[u]$. A clash (same colour on both ends of an edge) means no valid 2-colouring exists.

(a) Colour by walking: $1=0,2=1,3=0,4=1,5=0$. No edge repeats a colour → bipartite. $L=\{1,3,5\}$, $R=\{2,4\}$. A path has no cycle at all, so certainly no odd cycle. (Panel (a): all edges black.)

(b) $1=0,2=1$, then edge $(2,3)$ forces $3=0$, but edge $(3,1)$ has both $0$ → clash. The cycle has length 3 (odd) → not bipartite. (Panel (b): the red edge $(3,1)$ is the clash.)

(c) $1=0,2=1,3=0,4=1$; edge $(4,1)$ is $1$ vs $0$ ✅. Cycle length 4 (even) → bipartite. $L=\{1,3\}$, $R=\{2,4\}$.

(a) Both edges touch $x$ → they share an endpoint → not a matching.

(b) Endpoints used: $a,y,b,x,c,z$ — all distinct → valid matching of size $3$.

We reuse the colouring rule from L1.1 (labels $0$/$1$ are just the two classes). Start $1=0$. Force: $2=1$, $3=0$, $4=1$, $5=0$. Now the closing edge $(5,1)$: colour$[5]=0$, colour$[1]=0$ → same colour → clash (the red edge in the figure). $C_5$ is an odd cycle (length 5) → not bipartite. It is triangle-free yet still fails — the classic warning.

Kuhn's algorithm runs a DFS from each free left vertex, trying to trace an augmenting path. Process left vertices in order.

• $a$: free neighbour $x$ → match $a-x$. $M=\{a-x\}$.
• $b$: neighbour $x$ is taken by $a$. DFS tries to re-route: $b\to x\to a$ (matched), then $a$'s other edge $a\to y$ ($y$ free). Augmenting path $b-x-a-y$. Flip: $b-x$, $a-y$ matched; $a-x$ freed. $M=\{b-x,a-y\}$.
• $c$: free neighbour $z$ → match $c-z$. $M=\{b-x,a-y,c-z\}$.

Size $=3$. Since $|L|=3$ and all of $L$ is matched, this is a perfect matching — maximum.

• Phase 1: all lefts free, all rights free. The BFS finds that any single edge to a free right is an augmenting path of length 1 (one unmatched edge — odd, as required). DFS augments $a-x$; then $b$'s only edge $x$ is used this phase, so the phase yields $+1$.
• Phase 2: free left $b$, free right $y$. BFS finds the shortest augmenting path must bounce through the matched edge: $b-x$ (free) $\to x-a$ (matched) $\to a-y$ (free) = length 3. DFS augments → matching $\{b-x,a-y\}$.
• Phase 3: no free left remains → BFS finds nothing → stop.

Length sequence: $1,3$. It strictly increased by 2 — the Hopcroft–Karp guarantee. Because augmenting paths have odd length ($2k+1$), the shortest length rises by at least 2 each phase. Total phases $=2\le 2\sqrt{|V|}=2\sqrt{4}=4$. ✔

(a) König's Theorem (bipartite only): $\text{min vertex cover}=\text{max matching}=3$.

(b) Complement identity: $\text{max independent set}=|V|-\text{min vertex cover}=6-3=3$.

Free lefts: $b$. Free rights: $x$.

• BFS layers from $b$ (dist 0). Unmatched edges out of $b$: $b-y$ → $y$ at dist 1. $y$ is matched (to $a$) so follow the matched edge $y-a$ → $a$ at dist 2. Unmatched edges out of $a$: $a-x$ → $x$ at dist 3; $x$ is free → augmenting path found at length 3 (odd ✓).
• DFS augment along $b-y-a-x$ (the red chain in the figure): flip edges. $b-y$ and $a-x$ become matched; $a-y$ freed.
• New matching: $M=\{b-y,a-x,c-z\}$, size $3$ (up from $2$).

All of $L$ matched → this is maximum (perfect on the left).

When BFS finds a clash on edge $(u,v)$ with colour$[u]=$colour$[v]$, both $u$ and $v$ were reached from the same start via BFS-tree paths. Walk the tree path $\text{start}\to u$, cross edge $(u,v)$, walk back $v\to \text{start}$. Since $u,v$ share a colour, the two tree paths have the same parity of length; adding the extra edge $(u,v)$ makes the total cycle length odd. That cycle is the odd-cycle certificate.

For $C_5$: clash on $(5,1)$. Tree path $1\to 2\to 3\to 4\to 5$ plus edge $(5,1)$ gives the cycle $1-2-3-4-5-1$ of length 5 — odd. Certificate delivered.

Let $\ell$ = shortest augmenting-path length measured in edges. By (i), after $k$ phases $\ell \ge 2k+1$ (it starts at $1$ and rises by $\ge 2$ each phase).

Stage A — phases until $\ell >\sqrt{|V|}$. How many phases is that? We need $2k+1>\sqrt{|V|}$, i.e. $k>\frac{\sqrt{|V|}-1}{2}$. So once $k$ reaches $\lceil \frac{\sqrt{|V|}-1}{2}\rceil \le \frac{1}{2}\sqrt{|V|}$, the shortest length has passed $\sqrt{|V|}$. That is at most $\frac{1}{2}\sqrt{|V|}$ phases in Stage A.

Berge's lemma (the decomposition we need for Stage B). Let $M$ be the current matching and $M^{\ast }$ a maximum matching. Consider the symmetric difference $M△M^{\ast }$ = edges in exactly one of the two matchings. Look at the degree of any vertex in this edge set: it touches at most one edge of $M$ and at most one edge of $M^{\ast }$, so its degree is at most 2. A graph whose every vertex has degree $\le 2$ is a disjoint union of simple paths and cycles. Along any such path or cycle the edges must alternate between $M$ and $M^{\ast }$ (two $M$-edges can't meet at a vertex, nor two $M^{\ast }$-edges). The cycles have equal counts of each, but every path whose two ends are unmatched-in-$M$ is exactly an augmenting path for $M$. So $M△M^{\ast }$ decomposes into vertex-disjoint augmenting paths (plus alternating cycles that don't help). This is Berge's lemma. The number of these augmenting paths equals $|M^{\ast }|-|M|$ = the augmentations still owed.

Stage B — the tail, once $\ell >\sqrt{|V|}$. Each remaining augmenting path has more than $\sqrt{|V|}$ edges, so it visits more than $\sqrt{|V|}$ vertices (a chain of $\ell$ edges has $\ell +1$ distinct vertices $>\sqrt{|V|}$). By Berge's lemma these paths are vertex-disjoint, so they carve the $|V|$ vertices into disjoint groups each of size $>\sqrt{|V|}$. You cannot fit more than $\frac{|V|}{\sqrt{|V|}}=\sqrt{|V|}$ disjoint groups of that size into $|V|$ vertices. Hence at most $\sqrt{|V|}$ augmenting paths remain, and since each phase removes at least one, Stage B needs at most $\sqrt{|V|}$ phases.

Sum the two stages. $\text{total phases}\le \underset{\text{Stage A}}{\underbrace{\frac{1}{2}\sqrt{|V|}}}+\underset{\text{Stage B}}{\underbrace{\sqrt{|V|}}}=\frac{3}{2}\sqrt{|V|}\le 2\sqrt{|V|}.$ Each phase is one BFS + one DFS sweep $=O(E)$, so total work is $O\left(E\sqrt{|V|}\right)$ — the famous Hopcroft–Karp bound.

Hopcroft–Karp relies on the bipartite structure so that alternating BFS layers are consistent: matched/unmatched edges alternate cleanly across the $L/R$ divide. In a graph with odd cycles (blossoms) an augmenting path can enter and leave the same odd cycle, and the naive alternating search may miss it — a vertex can appear in a layer with the "wrong" parity. The fix is to contract each blossom into a single super-vertex, search, then expand. That is the Blossom Algorithm (Edmonds), which handles general graphs in polynomial time. Maximum Flow and König/Hall arguments only give the clean bipartite guarantees.

Bipartite iff no odd cycle ::: True — 2-coloring succeeds exactly when there is no odd cycle. Augmenting path length parity ::: Always odd (one more unmatched edge than matched). Hopcroft–Karp complexity ::: $O(E\sqrt{V})$. König's theorem scope ::: Bipartite graphs only; max matching = min vertex cover. Tool for general-graph matching ::: Blossom (Edmonds) algorithm.