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

1. What is a bipartite graph?

WHY do we care? Tons of real problems are "two kinds of things matched together": jobs↔workers, students↔projects, left pixels↔right pixels. Bipartiteness is the structural property that makes matching efficiently solvable.

2. The 2-Coloring Test (deciding bipartiteness)

Derivation from first principles. Coloring is a constraint system: each edge demands $c_u \ne c_v$ over $\{0,1\}$ . With only 2 colors, " $\ne$ " means $c_v = 1-c_u$ — a deterministic rule once one vertex is fixed. So within a connected component there are only two valid colorings (swap all colors), determined by the start. BFS/DFS just applies this forced rule; a clash means no assignment exists.

function isBipartite(G):
    color = array of -1 for all vertices   # -1 = uncolored
    for each vertex s with color[s] == -1: # handle disconnected graph
        color[s] = 0
        queue = [s]
        while queue not empty:
            u = queue.pop()
            for v in neighbors(u):
                if color[v] == -1:
                    color[v] = 1 - color[u] # WHY: force opposite
                    queue.push(v)
                elif color[v] == color[u]:
                    return false            # WHY: same color on an edge = odd cycle
    return true

Complexity: each vertex/edge touched once → $O(V+E)$ .

3. Bipartite Matching — the problem

Hungarian-style baseline (Kuhn's algorithm)

Repeatedly DFS from each free left vertex to find an augmenting path; augment. $O(V\cdot E)$ .

4. Hopcroft–Karp — doing it fast

HOW each phase works:

BFS from all free left vertices simultaneously, building a layered graph (distance levels) using alternating edges. This finds the shortest augmenting distance.
DFS through these layers to greedily extract a maximal set of vertex-disjoint shortest augmenting paths; augment each.
Repeat until BFS finds no free right vertex (no augmenting path → maximum, by Berge).

HopcroftKarp(L, R, adj):
    matchL = [None]*|L|;  matchR = [None]*|R|
    result = 0
    while BFS_builds_layers():        # phase: layered graph of shortest aug paths
        for u in L if matchL[u] is None:
            if DFS_augment(u):        # find vertex-disjoint shortest aug path
                result += 1
    return result
# BFS sets dist[] for free-left layer-by-layer; DFS only follows increasing layers

Worked example Tiny matching (two phases)

$L=\{a,b\}$ , $R=\{x,y\}$ , edges $a\!-\!x, a\!-\!y, b\!-\!x$ . Start with empty matching.

Phase 1 BFS: free lefts $a,b$ at dist 0. Edges to free rights $x,y$ give shortest augmenting length 1. The layered graph only contains these length-1 paths.
Phase 1 DFS (maximal disjoint set of length-1 paths): take $a\to x$ → match $a\!-\!x$ . Now try $b$ : its only neighbor $x$ is already used in this phase, so no vertex-disjoint length-1 path remains for $b$ . Why stop? Within one phase we only use shortest, vertex-disjoint paths. Phase 1 yields +1. Current matching: $\{a\!-\!x\}$ .
Phase 2 BFS: only free left is $b$ (and free right $y$ ). Shortest augmenting path now has length 3 (it must bounce through matched edge $a\!-\!x$ ): $b\to x$ (unmatched), $x\to a$ (matched edge), $a\to y$ (unmatched). Why length grew? Exactly the Hopcroft–Karp guarantee: shortest augmenting length strictly increases each phase.
Phase 2 DFS: augment along $b\!-\!x\!-\!a\!-\!y$ : flip edges → now $b\!-\!x$ and $a\!-\!y$ matched, $a\!-\!x$ freed. +1. Matching: $\{b\!-\!x,\ a\!-\!y\}$ .
Phase 3 BFS: no free left vertex remains → stop. Result = 2 (perfect matching). ✅

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

5. König's Theorem (the bonus you can derive answers from)

Common mistakes

Recall Feynman: explain to a 12-year-old

Imagine a dance where boys stand on the left, girls on the right, and a hand-link only goes boy↔girl, never boy↔boy. That's a bipartite graph: two teams, links only across. To check it, paint someone red, all their friends blue, their friends red again — if two friends ever end up the same color, the "two teams" plan fails (there's an odd loop of friends). Matching is pairing each boy with one girl so nobody is double-booked. The clever Hopcroft–Karp trick: in each round it grabs a bunch of the shortest non-overlapping "swap chains" at once; the chains get longer round by round, so the whole pairing finishes super fast.

Connections

Graph Coloring — bipartite = 2-colorable special case (chromatic number $\le 2$ ).
BFS / DFS — engine of the 2-coloring test and the phases.
Maximum Flow — bipartite matching reduces to max-flow (unit-capacity source→L→R→sink).
Berge's Theorem — augmenting-path optimality condition.
König's Theorem — matching ⟷ vertex cover ⟷ independent set duality.
Blossom Algorithm — matching in general (non-bipartite) graphs.

Flashcards

A graph is bipartite if and only if it has no ...

odd-length cycle.

2-coloring propagation rule for edge (u,v)

color[v] = 1 − color[u].

Time complexity of the BFS/DFS 2-coloring bipartiteness test

O(V + E).

Definition of a matching

a set of edges with no two sharing a vertex.

What is an augmenting path?

a path between two unmatched vertices alternating unmatched/matched edges (odd length, one extra unmatched edge).

Berge's theorem

a matching is maximum iff it has no augmenting path.

Effect of flipping edges along an augmenting path

matching size increases by exactly 1.

Hopcroft–Karp core idea

each phase finds a maximal set of shortest vertex-disjoint augmenting paths via BFS layering + DFS, then augments all.

In one Hopcroft–Karp phase, which augmenting paths are used?

only a maximal set of SHORTEST, vertex-disjoint augmenting paths; longer/overlapping ones wait for later phases.

Time complexity of Hopcroft–Karp

O(E√V).

Why only O(√V) phases in Hopcroft–Karp?

shortest augmenting path length strictly increases each phase, so after √V phases only O(√V) augmentations remain.

König's theorem (bipartite)

max matching size = min vertex cover size.

Max independent set in bipartite graph in terms of matching

|V| − max matching size.

Why must you loop over all vertices in the 2-coloring test?

to handle disconnected components.

Why can't Hopcroft–Karp be used on general graphs?

odd cycles (blossoms) break the bipartite layered structure; use the Blossom algorithm instead.

Concept Map

Hinglish (regional understanding)

Intuition Hinglish mein samjho

Bipartite graph ka matlab simple hai: vertices ko do teams mein baant do (L aur R) aise ki har edge sirf alag teams ke beech ho, kabhi same team ke andar nahi. Isko check karne ka tareeka — 2-coloring: kisi vertex ko color 0 do, uske saare neighbors ko 0 ka ulta (color 1) do, aage propagate karte jao (BFS/DFS se). Agar kabhi ek edge ke dono ends same color ho gaye, toh graph bipartite nahi hai. Yaad rakho golden rule: graph bipartite hai agar aur sirf agar usme koi odd-length cycle nahi ho. Triangle (3 ka loop) ya pentagon (5 ka loop) bipartite nahi hote.

Matching ka problem yeh hai: L ke logon ko R ke logon se pair karo, par koi bhi do baar use na ho (jaise workers ko jobs assign karna). Maximum matching matlab maximum pairs. Iske liye augmenting path dhoondte hain — ek alternating chain jo do free vertices ko jodti hai. Us chain par matched/unmatched edges flip kar do, toh matching ek se badh jaata hai. Berge ka theorem kehta hai: jab koi augmenting path nahi bachta, tab matching maximum ho gaya.

Hopcroft–Karp isi idea ka fast version hai. Normal Kuhn algorithm ek baar mein ek hi path fix karta hai. Hopcroft–Karp ek phase mein BFS se sirf shortest augmenting paths ki layers banata hai, phir DFS se ek saath kayi vertex-disjoint shortest paths nikaal ke augment karta hai. Dhyan rakho: ek phase mein sirf shortest aur non-overlapping paths hi lete hain; lambe ya overlapping paths agle phases ke liye wait karte hain. Hamare chhote example mein Phase 1 mein sirf $a\!-\!x$ banta hai, aur $b$ ko Phase 2 mein length-3 path $b\!-\!x\!-\!a\!-\!y$ se match karte hain. Har phase mein shortest path ki length badhti hai, isliye sirf $O(\sqrt V)$ phases lagte hain aur total time ban jaata hai $O(E\sqrt V)$ — bohot tez. Caution: yeh sirf bipartite graphs par chalta hai; general graphs ke liye Blossom algorithm chahiye. Bonus: König theorem se max matching nikaalte hi min vertex cover aur max independent set bhi free mein mil jaate hain.

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

1. What is a bipartite graph?

2. The 2-Coloring Test (deciding bipartiteness)

3. Bipartite Matching — the problem

Hungarian-style baseline (Kuhn's algorithm)

4. Hopcroft–Karp — doing it fast

5. König's Theorem (the bonus you can derive answers from)

Common mistakes

Connections

Flashcards

Concept Map

Hinglish (regional understanding)

Go deeper — visual, from zero

Test yourself — Graphs

Connections