Day 65 — Bipartite graphs & matchings

Updated

July 30, 2026

Day 65 — Bipartite graphs & matchings

Stage VI · concept day
Goal: Characterize bipartite graphs via 2-coloring and odd cycles; define matchings and maximum matchings; state Hall’s marriage theorem with a small example; König’s theorem awareness.

Why this matters

Bipartite graphs model jobs↔︎machines, students↔︎projects, clients↔︎servers, and users↔︎items. Matchings answer assignment problems. Hall’s theorem is the classical existence criterion; coloring links to scheduling (Day 67). Many NP-hard problems become tractable on bipartite graphs.

Theory

Bipartite graph

\(G=(V,E)\) is bipartite if \(V=L\cup R\) with \(L\cap R=\emptyset\) and every edge has one end in \(L\) and one in \(R\) (no edge inside \(L\) or inside \(R\)).

Complete bipartite \(K_{m,n}\): all edges between parts of sizes \(m,n\).

2-coloring characterization

Theorem. \(G\) is bipartite ⇔ \(G\) is 2-colorable (vertices colorable with 2 colors so every edge is bichromatic) ⇔ \(V\) splits into two independent sets.

Colors = the two parts.

Odd cycle characterization

Theorem. \(G\) is bipartite ⇔ \(G\) contains no odd cycle.

Proof sketch.

  • \((\Rightarrow)\) Odd cycle not 2-colorable.
  • \((\Leftarrow)\) Each component: BFS color by layer parity; conflict edge ⇒ odd cycle (standard argument).

Algorithm: BFS/DFS 2-color; fail ⇒ odd cycle witness.

Forests and trees

Every tree (forest) is bipartite—no cycles at all.

Matchings

A matching \(M\subseteq E\) is a set of edges with no two sharing a vertex.
Saturated vertex: incident to an edge of \(M\).
Maximum matching: matching of largest cardinality.
Maximal matching: cannot add another edge (local); may not be maximum.
Perfect matching: saturates all vertices (\(|V|\) even necessary).
\(L\)-perfect / matching saturating \(L\): every vertex of \(L\) matched (common in bipartite assignment).

Alternating and augmenting paths (lite)

Given matching \(M\): an alternating path alternates edges in \(M\) and not in \(M\).
Augmenting path: alternating path starting and ending at free (unsaturated) vertices.
Berge’s lemma: \(M\) maximum ⇔ no \(M\)-augmenting path.
Hopcroft–Karp / Hungarian culture: algorithms find max matchings—awareness; hand-find augmenting paths on tiny graphs.

Hall’s marriage theorem

Setting: bipartite \(G=(L\cup R,E)\).

For \(S\subseteq L\), write \(N(S)=\{r\in R:\exists \ell\in S,\ \{\ell,r\}\in E\}\).

Theorem (Hall). There exists a matching that saturates every vertex of \(L\) if and only if

\[ \forall S\subseteq L,\quad |N(S)|\ge |S|. \]

(Hall’s condition.)

Necessity: obvious—\(S\) needs ≥\(|S|\) distinct neighbors to match.
Sufficiency: classical proof via maximality / Konig—or augmenting paths; accept and use.

Small check: always verify singleton neighbors and full \(L\).

König’s theorem (awareness)

In bipartite graphs, size of maximum matching = size of minimum vertex cover (vertices hitting all edges).
Does not hold for general graphs (gap possible).

System of distinct representatives

Hall’s theorem rephrases SDR existence for families of sets—same combinatorics.

Why bipartite matching is “easy” (culture)

Maximum matching in general graphs is still polynomial (Edmonds’ blossom algorithm)—but much more complex. Bipartite case reduces to network flow or Hopcroft–Karp; hand proofs use augmenting paths cleanly because alternating cycles behave well. Hall’s condition is combinatorial, not algorithmic, but explains existence.

Independent sets and bipartitions

In a bipartite graph with parts \(L,R\), both \(L\) and \(R\) are independent sets. Conversely, a graph is bipartite iff \(V\) is the union of two independent sets (possibly after placing isolates either side).

Counting perfect matchings (lite)

For \(K_{n,n}\), perfect matchings ↔︎ permutations: \(n!\).
For a general bipartite graph, counting perfect matchings is \(\#P\)-complete—harder than finding one. Finding vs counting diverge.

Worked examples

Example 1 — Bipartite check

\(C_4\): bipartite. \(C_5\): odd cycle—not bipartite. \(K_3\): not.

Example 2 — 2-color BFS

Star: center color 1, leaves color 2—OK.

Example 3 — Matching

\(K_{2,3}\): maximum matching size 2 (min part). No perfect matching (\(|V|=5\) odd).

Example 4 — Maximal not maximum

Path of 3 edges: middle edge alone is maximal matching size 1; maximum size 2 (two ends).

Example 5 — Hall success

\(L=\{a,b\}\), \(R=\{1,2,3\}\), edges \(a{-}1,a{-}2,b{-}2,b{-}3\).
\(N(\{a\})=2\), \(N(\{b\})=2\), \(N(L)=3\ge 2\). Matching exists e.g. \(a{-}1,b{-}3\).

Example 6 — Hall failure

\(L=\{a,b,c\}\), all only connected to \(\{1,2\}\). Then \(N(L)=2<3\)—no \(L\)-saturating matching.

Example 7 — Hall subtle

\(L=\{a,b,c\}\), \(N(\{a,b\})=\{1\}\) only both to 1, \(c\) to 2,3. \(|N(\{a,b\})|=1<2\)—fail even if \(|N(L)|\ge 3\).

Example 8 — Perfect matching \(K_{n,n}\)

\(n!\) perfect matchings (permutations).

Example 9 — Augmenting path

Path \(u{-}v{-}w{-}x\) with \(M=\{v{-}w\}\), free \(u,x\): path is augmenting; flip → \(\{u{-}v,w{-}x\}\).

Example 10 — Tree matching

Path \(P_4\): max matching 2.

Example 11 — Job assignment

3 workers, 3 jobs, bipartite edges = qualifications; Hall checks existence of full assignment.

Example 12 — Odd cycle witness

Conflict in 2-coloring: two adjacent same color ⇒ walk of even length between them + edge = odd closed walk ⇒ odd cycle exists.

Example 13 — Non-bipartite matching

Triangle: max matching size 1; vertex cover size 2; König fails (1≠2).

Example 14 — \(K_{1,n}\)

Max matching 1; Hall for \(L=\) leaves fails if \(|L|>1\) and \(L\) is the leaf part with \(|R|=1\).

Example 15 — Complete \(K_{m,n}\)

Max matching \(\min(m,n)\).

Example 16 — Full Hall check small

\(L=\{a,b,c\}\), \(R=\{1,2,3\}\), edges: \(a{-}1,a{-}2,b{-}2,b{-}3,c{-}3\).
Singletons: each has \(\ge 1\) neighbor. Pairs: \(N(\{a,b\})=\{1,2,3\}\), \(N(\{a,c\})=\{1,2,3\}\), \(N(\{b,c\})=\{2,3\}\). Full \(L\): \(N(L)=\{1,2,3\}\). Hall OK. Matching: \(a{-}1,b{-}2,c{-}3\).

Example 17 — König equality

Same graph: max matching size \(3\); min vertex cover size \(3\) (e.g. \(\{1,2,3\}\) or better \(\{a,b,c\}\)—actually \(\{1,2,3\}\) covers; smaller: \(\{a,2,c\}\)? Check. A cover of size 3 matches König when matching size 3.

Example 18 — SDR

Sets \(A_1=\{1,2\}\), \(A_2=\{2\}\), \(A_3=\{2,3\}\). Hall for family: need distinct reps. \(A_2\) forces \(2\); then \(A_1\to 1\), \(A_3\to 3\). OK.

Example 19 — Non-example Hall

\(A_1=A_2=\{1\}\): \(|N(\{1,2\})|=1<2\)—no SDR.

Example 20 — Maximal matching trap

In \(P_3\) (3 edges? \(P_4\) has 3 edges): vertices \(1{-}2{-}3{-}4\), matching \(\{2{-}3\}\) maximal size 1; maximum \(\{1{-}2,3{-}4\}\) size 2. Always look for augmenting paths before declaring maximum.

Exercises

  1. Define bipartite; give 3 examples and 2 non-examples.
  2. Prove: odd cycle ⇒ not bipartite.
  3. 2-color \(K_{2,4}\); show \(C_6\) bipartite.
  4. Prove trees are bipartite.
  5. Maximum matching in \(C_6\); in \(C_5\).
  6. Maximal vs maximum: draw an example gap.
  7. Hall: verify Ex. 5 fully for all \(S\).
  8. Hall fail Ex. 6: exhibit violating \(S\).
  9. Does \(K_{2,3}\) have matching saturating the side of size 2? Size 3?
  10. Count perfect matchings of \(K_{3,3}\).
  11. Hand-find max matching via augmenting paths on a 6+6 bipartite graph you draw.
  12. König awareness: max matching = min cover on your bipartite example—check sizes.
  13. CS: assign 4 processes to 4 cores with constraints—model bipartite.
  14. True/false: every regular bipartite graph has a perfect matching (yes if \(k\)-reg and equal parts—Hall).
  15. Prove necessity of Hall’s condition.
  16. BFS bipartite test algorithm steps.
  17. Matching size ≤ \(|V|/2\) always.
  18. Edge cover vs matching Gallai identities awareness optional.
  19. When is \(K_{m,n}\) Hamiltonian? (\(m=n\ge 2\)) preview Day 66.
  20. System of distinct representatives: 3 sets example.
  21. Challenge: prove no augmenting path ⇒ maximum (Berge) sketch.
  22. Find all maximum matchings of \(P_5\).
  23. Odd wheel: not bipartite.
  24. Construct bipartite with Hall OK for all \(|S|\le 2\) but fail larger—standard.
  25. Portfolio: one Hall success + one fail writeup exam quality.

CS connection

  • Task assignment / load pairing.
  • Bipartite recommendation graphs.
  • Register allocation cousin is coloring (Day 67); matching for other resources.
  • Network flow reduces bipartite matching (awareness).
  • Stable marriage is a different matching model (preferences)—name only.

Common pitfalls

Pitfall What to do instead
Checking only \(|N(L)|\ge|L|\) Check all \(S\subseteq L\)
Maximal = maximum Augmenting paths
Perfect matching on odd \(\|V\|\) Impossible
Coloring multipartite as bipartite Exactly 2 parts
Applying König to non-bipartite Counterexample triangle

Checkpoint

  • Bipartite ⇔ no odd cycle ⇔ 2-colorable
  • Matching vocabulary
  • Hall’s theorem statement + small use
  • Augmenting path flip
  • König awareness one sentence
  • Exercises 1–15
  • One Hall failure diagnosed

Two personal takeaways:

  1. …
  2. …

Selected mini-solutions

  1. \(C_6\): 3; \(C_5\): 2.
  2. Yes for size 2; no for size 3.
  3. \(3!=6\).
  4. True for \(k\ge 1\) balanced \(k\)-regular bipartite—Hall holds.
  5. Yes.

Deepening notes

2-color BFS procedure

  1. Start at \(s\), color 0.
  2. Queue BFS; color neighbors opposite.
  3. If neighbor already colored same as current → odd cycle.
  4. Restart on other components.

Hall checklist for small \(L\)

For \(|L|\le 4\), verify all \(2^{|L|}-1\) nonempty subsets—or argue by structure (e.g. expanders, complete bipartite).

Augmenting path flip

Along free–M–free alternating path, symmetric difference with \(M\) increases matching size by 1. Repeat until none—maximum.

Extra drills

D1. 2-color \(K_{3,3}\).
D2. Find odd cycle in utility graph drawing crossings.
D3. Max matching \(C_7\).
D4. Hall all subsets for a 3+3 bipartite you draw.
D5. Violating \(S\) for a failed matching.
D6. Perfect matchings of \(K_{2,2}\).
D7. König on a small bipartite: matching size = cover size.
D8. Triangle: matching 1, cover 2—König fails.

Flash

bipartite ⇔ no odd cycle ⇔ 2-colorable; Hall \(\forall S\subseteq L:|N(S)|\ge|S|\); augmenting path ⇔ not maximum.

Exam drill block

E1. Prove odd cycle ⇒ not 2-colorable.
E2. BFS 2-color a tree and a \(C_6\).
E3. Find max matching by augmenting paths on a path of length 5.
E4. Hall verify complete \(K_{2,4}\) saturating left.
E5. Hall fail: draw and mark \(S\).
E6. Perfect matchings of \(K_{3,3}\).
E7. König check sizes on a small bipartite.
E8. Why triangle violates König equality.
E9. Job assignment 4×4 with one isolated job—Hall?
E10. True/false: (i) trees bipartite (ii) maximal matching = maximum (iii) Hall only needs \(|N(L)|\ge|L|\).

Mini solutions

E3. Size 3.
E6. \(6\).
E10. T; F; F.

Deep dive — From Hall to algorithms

Hall’s theorem is non-constructive as usually stated: it does not build the matching. Augmenting-path algorithms construct a maximum matching and, when no \(L\)-saturating matching exists, the theory of barriers produces a violating set \(S\) (by analyzing the final unsaturated structure). In interviews, always: (1) model bipartite, (2) check small Hall sets by hand, (3) flip augmenting paths on a drawing.

Synthesis

Bipartite ⇔ 2-colorable ⇔ no odd cycle. Matchings pair vertices without sharing. Maximum ≠ maximal; augmenting paths close the gap. Hall’s condition is the existence criterion for saturating one side. König equates matching number and cover number only in the bipartite world—triangle is the warning shot.

S1. Prove: if \(G\) has an odd closed walk, then \(G\) has an odd cycle.
S2. 2-color \(K_{2,5}\) and state \(\chi\).
S3. Exhibit a violating Hall set in a 4+4 bipartite graph of your design with max matching \(<4\).
S4. Hand-run augmenting paths to a maximum matching on a path of 7 vertices.
S5. Count perfect matchings of \(K_{2,2}\) and of a tree that is a path \(P_4\).

Tomorrow

Day 66 — Euler & Hamilton: Euler circuits characterization; Hierholzer idea; Hamilton hardness; Dirac/Ore statements.