Day 23 — Bipartite, Euler/Hamilton & Graph Coloring

Updated

July 30, 2025

Day 23 — Bipartite, Euler/Hamilton & Graph Coloring

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

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

Two personal takeaways:

Selected mini-solutions

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

Deepening notes

2-color BFS procedure

Start at \(s\), color 0.
Queue BFS; color neighbors opposite.
If neighbor already colored same as current → odd cycle.
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.

Day 66 — Euler & Hamilton paths

Stage VI · concept day
Goal: Characterize Eulerian circuits/trails; Hierholzer idea; contrast Hamilton paths/cycles with NP-hardness awareness; state Dirac and Ore sufficient conditions.

Why this matters

Euler: traverse every edge exactly once (Chinese Postman, routing inspection).
Hamilton: visit every vertex exactly once (TSP culture).
Euler is easy (degree conditions + linear algorithms). Hamilton is hard in general (NP-complete decision). Knowing which problem you face saves careers.

Theory

Eulerian trails and circuits

In an undirected multigraph:

Eulerian circuit (tour): closed trail containing every edge exactly once.
Eulerian trail: (possibly open) trail containing every edge exactly once.

Theorem (Euler — undirected).

\(G\) has an Eulerian circuit ⇔ \(G\) is connected (up to isolated vertices) and every vertex has even degree.
\(G\) has an Eulerian trail but not necessarily a circuit ⇔ connected and exactly zero or two vertices of odd degree.
- Zero odds ⇒ circuit.
- Two odds ⇒ trail starts at one odd and ends at the other.

Proof sketch (circuit).

\((\Rightarrow)\) Enter/leave pairs force even degrees; connectivity for edges.
\((\Leftarrow)\) Hierholzer: start at a vertex; build a trail until stuck (must be start if all even); if unused edges remain, they form an even-degree subgraph in a connected component of remainder—splice a detour tour into the main tour; repeat.

Directed version (lite): strongly connected (weakly + balanced) and \(\mathrm{deg}^+=\mathrm{deg}^-\) at every vertex for Eulerian circuit.

Hierholzer’s algorithm (idea)

Start at \(v\); form a closed trail by unused edges until return.
While unused edges: start from a vertex on current tour that has unused edges; form another closed trail; splice.
Result is Eulerian circuit.

Hand-simulate on small multigraphs.

Chinese Postman (lite awareness)

If not all even: add duplicate edges of minimum cost pairing odd-degree vertices (perfect matching on odd set)—then Eulerian. Polynomial for undirected.

Hamiltonian paths and cycles

Hamilton path: path visiting every vertex exactly once.
Hamilton cycle: cycle through every vertex exactly once.

No simple efficient characterization known (unlike Euler).
Decision problem is NP-complete (for general graphs)—awareness: hard in worst case; small instances solvable by hand/backtrack.

Sufficient conditions (not necessary)

Dirac’s theorem (1952). If \(G\) is simple on \(n\ge 3\) vertices and \(\deg(v)\ge n/2\) for every \(v\), then \(G\) has a Hamilton cycle.

Ore’s theorem (1960). If \(n\ge 3\) and for every pair of nonadjacent vertices \(u,v\), \(\deg(u)+\deg(v)\ge n\), then \(G\) has a Hamilton cycle.

Both imply high connectivity and many edges—strong hypotheses.
Not necessary: \(C_n\) is Hamiltonian but degrees are 2, far below \(n/2\) for large \(n\).

Bipartite Hamilton

\(K_{m,n}\) has Hamilton cycle ⇔ \(m=n\ge 2\).
Hamilton path if \(|m-n|\le 1\).

Relationship summary

	Euler	Hamilton
Object used once	edges	vertices
Characterization	clean (degrees)	none simple
Complexity	poly-time	NP-complete decide
Classic theorems	Euler 1736	Dirac, Ore (sufficient)

TSP culture

Traveling Salesman: min weight Hamilton cycle in weighted complete graph—NP-hard optimization. Metric TSP approximable—awareness only.

Necessity of even degrees (detail)

Proof. In an Eulerian circuit, every time the tour enters a vertex via an edge it must leave via a different edge—pairing the incident edges. Hence degree even at every vertex. At the start/end (same vertex), the first departure and last arrival also pair. For an open Eulerian trail, the start has one unpaired departure and the end one unpaired arrival → exactly those two vertices odd degree. \(\square\)

Handshaking corollary

The number of odd-degree vertices is always even. So the Euler trail condition “0 or 2 odds” is the only possible small counts; 1 or 3 odds can never occur.

Gray codes and hypercubes

The \(n\)-dimensional hypercube \(Q_n\) has a Hamilton path/cycle (for \(n\ge 2\) cycle): binary reflected Gray codes list all \(n\)-bit strings so consecutive codes differ by one bit—exactly a Hamilton path in \(Q_n\). Important for error-resistant coding and hardware state tours.

Worked examples

Example 1 — \(K_2\)

Two verts one edge: Eulerian trail yes; circuit no (odds). Not Hamilton cycle (\(n<3\)).

Example 2 — \(C_n\)

Eulerian circuit (2-regular even); Hamilton cycle (itself).

Example 3 — \(K_4\)

Degrees 3 (odd): no Euler circuit; all deg odd (4 vertices odd)—no Euler trail either? Four odds: no Euler trail (need 0 or 2 odds). Hamilton: yes (\(K_n\) for \(n\ge 3\) Hamiltonian).

Example 4 — House graph

Square with roof triangle: check degrees for Euler; often one trail.

Example 5 — Hierholzer

Two edge-disjoint cycles sharing a vertex: tour one cycle, splice the other at shared vertex.

Example 6 — Exactly two odds

Path \(P_n\): two odds (ends); Eulerian trail = the path itself if no extra edges; actually \(P_n\) has \(n-1\) edges, trail visits all edges yes.

Example 7 — Dirac applies

\(K_n\) degrees \(n-1\ge n/2\) for \(n\ge 2\)—has Hamilton cycle for \(n\ge 3\).

Example 8 — Dirac fails hypothesis but Hamilton

\(C_5\): deg \(2<2.5\); still Hamilton. Dirac not necessary.

Example 9 — Ore check

Graph: nonadjacent pair with deg sum \(<n\) may still be Hamiltonian—Ore sufficient only.

Example 10 — \(K_{2,3}\)

No Hamilton cycle (unequal parts). Hamilton path: yes (start in size 3).

Example 11 — Petersen graph awareness

Famous non-Hamiltonian 3-regular graph—optional name.

Example 12 — Directed Euler

Cycle digraph: balanced, Eulerian circuit.

Example 13 — Add edge for Euler

Two odds: add edge between them (if missing) creates Euler circuit in multigraph sense—Chinese postman pair.

Example 14 — Complete bipartite equal

\(K_{3,3}\): Hamilton cycle alternates parts.

Example 15 — Complexity contrast

Checking all degrees even: \(O(n)\). Searching Hamilton: exponential naive \(n!\).

Example 16 — Degree table diagnosis

Graph degrees \((2,2,2,2,4)\): all even → Euler circuit if connected. Degrees \((3,3,2,2,2)\): two odds → Euler trail. Degrees \((3,3,3,3)\): four odds → no Euler trail; Chinese postman pairs into two paths’ worth of duplicates.

Example 17 — Ore fails, still Hamiltonian

\(C_6\): nonadjacent vertices can have deg sum \(2+2=4<6\); Ore hypothesis fails; still Hamiltonian.

Example 18 — Hierholzer narrative

Multigraph: vertices \(A,B,C\); double edges \(AB\) and cycle \(A{-}B{-}C{-}A\). Start at \(A\), tour \(A{-}B{-}C{-}A\); residual double edge \(AB\) unused—at \(A\) or \(B\) on tour, splice \(A{-}B{-}A\) detour. Full Euler circuit uses every edge.

Example 19 — \(K_{m,n}\) Hamilton summary

Relation	Hamilton path	Hamilton cycle
\(m=n\ge 2\)	yes	yes
\(\|m-n\|=1\)	yes	no
\(\|m-n\|\ge 2\)	no	no

Example 20 — Eulerian but not Hamiltonian

Two copies of \(C_4\) sharing a single vertex: all degrees even (shared vertex deg 4); Eulerian circuit exists; no Hamilton cycle (cannot visit all vertices of both lobes in one cycle without repeating the cut vertex improperly—standard bowtie/barbell-with-point).

Exercises

State Euler circuit theorem fully.
State Euler trail theorem.
Which of \(K_3,K_4,K_5\) have Euler circuits? Euler trails?
\(K_{2,3}\) Euler? Hamilton path/cycle?
Prove necessity of even degrees for Euler circuit.
Hierholzer on a multigraph with 6 edges you draw.
Four odd-degree vertices: can you have Euler trail? What about open Chinese postman?
Define Hamilton path/cycle.
Show \(K_n\) (\(n\ge 3\)) is Hamiltonian.
Apply Dirac to a 6-vertex 3-regular graph—does hypothesis hold?
Give counterexample to converse of Dirac.
Ore: verify or refute on a small graph.
Why \(K_{1,3}\) has no Hamilton path? (It does: path through 3 leaves? Star \(K_{1,3}\) has 4 verts: path leaf-center-leaf leaves one leaf—no Hamilton path.)
\(K_{1,3}\) is a tree—Hamilton path ⇔ tree is a path.
CS: garbage truck routing ~ Euler/Chinese postman.
CS: TSP ~ Hamilton.
Directed: state Euler circuit condition.
Find an Euler trail in a graph with exactly two odds.
True/false: every Eulerian graph is Hamiltonian. (False: two cycles sharing a vertex.)
True/false: every Hamiltonian graph is Eulerian. (False: \(C_n\) with a chord may break even degrees.)
Challenge: prove that if all degrees even and connected, an Euler circuit exists (expand Hierholzer).
Count edge tours? Hard—skip.
Hamilton in hypercube \(Q_n\): yes (Gray codes).
NP-complete awareness: what does “no known poly algorithm” mean practically?
Portfolio: one Euler diagnosis + one Dirac/Ore application writeup.

CS connection

Network traversal / street sweeping / DNA fragment assembly (Euler in de Bruijn graphs).
TSP / vehicle routing (Hamilton hard).
De Bruijn sequences via Euler circuits in digraphs.
Compiler / FSM: state tours rare; edge coverage testing ~ Euler culture.
Gray codes as Hamilton paths in hypercubes.

Common pitfalls

Pitfall	What to do instead
Euler vs Hamilton confusion	Edges vs vertices
Ignoring connectivity for Euler	Require connected (ignore isolates)
Treating Dirac as necessary	Only sufficient
“Hard” means impossible	Means computational difficulty
Multigraph degrees for Euler	Allowed and natural

Checkpoint

Two personal takeaways:

Selected mini-solutions

\(K_3\): Euler yes (deg 2); \(K_4\) deg 3 no circuit no trail (4 odds); \(K_5\) deg 4 circuit yes.
Degrees 3,3,2,2,2: two odds—Euler trail yes; Hamilton path yes; cycle no.
Star \(K_{1,3}\): no Hamilton path.
False.
False.

Deepening notes

Degree parity quick tests

# odd-degree verts	Euler?
0	circuit (if connected)
2	trail start/end at odds
>2 even	no trail

Always even count by handshaking—never 1,3,5 odds.

Hierholzer splice picture

Tour \(T\) closed; at vertex \(v\) on \(T\) with unused edge, build tour \(T'\) in residual; replace \(v\) in \(T\) by \(T'\). Edges of \(T\cup T'\) used once.

Dirac/Ore memory

Dirac: every deg ≥ \(n/2\).
Ore: every nonedge \(uv\) has \(\deg u+\deg v\ge n\).
Both sufficient for Hamilton cycle; \(C_n\) shows not necessary.

Extra drills

D1. Euler status of \(K_{2,4}\).
D2. Hierholzer on two squares sharing a vertex.
D3. Hamilton path in \(K_{2,3}\).
D4. Does Dirac apply to \(K_{3,3}\)? (\(n=6\), deg 3≥3 yes—has cycle.)
D5. Ore fail example still Hamiltonian.
D6. Four odds: Chinese postman needs min pairing.
D7. Hypercube \(Q_3\) Hamilton cycle (Gray).
D8. Explain NP-complete for a non-theorist in 3 sentences.

Flash

Euler: even degrees; Hamilton: hard; Dirac \(\deg\ge n/2\); \(K_{m,n}\) cycle iff \(m=n\ge 2\).

Exam drill block

E1. Euler circuit/trail status for \(K_2,K_3,K_4,K_5,C_n,K_{2,3}\).
E2. Hierholzer narrative on a 2-cycle multiedge pair of loops figure.
E3. Prove necessity of even degrees for Euler circuit.
E4. Dirac: does it apply to \(K_{n,n}\)? Degrees \(n\) vs \(2n/2=n\)—yes equality; has cycle.
E5. Ore statement; give \(C_5\) as converse fail.
E6. Hamilton path/cycle in \(K_{3,3}\) and \(K_{2,3}\).
E7. Chinese Postman idea for two odds.
E8. TSP vs Hamilton decision—one sentence each.
E9. Why “Eulerian ⇒ Hamiltonian” is false (bowtie).
E10. Gray code = Hamilton path in \(Q_n\) awareness.

Mini solutions

E1. See theory table; \(K_4\) no trail; \(K_5\) circuit; \(K_{2,3}\) trail yes cycle no.
E6. \(K_{3,3}\) both; \(K_{2,3}\) path yes cycle no.
E9. Two triangles sharing a vertex: Eulerian if multigraph degrees even—use two cycles share vertex all even degrees Euler but not Hamilton if… standard: two \(K_3\) sharing vertex has Euler circuit in multigraph sense? Degrees 2,2,2,4,2,2—Euler yes; Hamilton visits all 5 verts hard—actually has no Hamilton cycle. Good.

Deep dive — Choosing the model

English	Graph object	Complexity vibe
Inspect every road	Euler trail/circuit	Easy (degrees)
Visit every city once	Hamilton path/cycle	Hard (NP-c)
Revisit roads OK, min length	Chinese postman	Poly undirected
Revisit cities OK, min length	Metric TSP etc.	Hard

Mislabeling “tour the neighborhood streets” as TSP is a classic modeling error—streets are edges (Euler), landmarks are vertices (Hamilton).

Synthesis

Euler cares about edges and degrees; Hamilton cares about vertices and has no simple iff criterion—only sufficient conditions (Dirac, Ore) and hardness. Hierholzer constructs Euler circuits by splicing tours. Bipartite Hamilton needs balanced parts for cycles. Always diagnose odd-degree counts first for edge tours.

S1. Full Euler diagnosis for \(K_{2,4}\) and \(K_{3,3}\).
S2. Prove necessity of even degrees for an Eulerian circuit (paragraph proof).
S3. Apply Dirac carefully to a 3-regular graph on 6 vertices—hypothesis? Hamilton?
S4. Explain why four odd-degree vertices forbid an Euler trail but allow a Chinese-postman pairing approach.
S5. Write a 5-sentence contrast of Euler vs Hamilton for a non-math stakeholder.

Tomorrow

Day 67 — Coloring & planarity: chromatic number; clique bound; 4-color theorem; Kuratowski/Wagner awareness; register allocation story.

Day 67 — Coloring & planarity

Stage VI · concept day
Goal: Define vertex coloring and chromatic number; use clique lower bounds; bipartite \(\chi=2\); state the four color theorem; Kuratowski/Wagner awareness; dual graphs lite; register allocation story.

Why this matters

Coloring models conflict-free assignment: exams, frequencies, registers, schedule slots. Planarity models chip layout and map drawing without crossings. The four color theorem is a landmark; register allocation is the killer CS application of coloring ideas (heuristics in practice).

Theory

Vertex coloring

A proper \(k\)-coloring of \(G\) assigns each vertex a color in \(\{1,\ldots,k\}\) so adjacent vertices get different colors.
Chromatic number \(\chi(G)\) = minimum \(k\) such that a proper \(k\)-coloring exists.

Independent set: no two adjacent—each color class is an independent set. Coloring = partition into independent sets.

Easy bounds

\(\chi(G)\le \Delta(G)+1\) (greedy coloring; Brooks’ theorem improves to \(\Delta\) except complete and odd cycles).
\(\chi(G)\ge \omega(G)\) where \(\omega(G)\) is the clique number (size of largest clique)—all clique vertices need distinct colors.
\(\chi(G)\ge n/\alpha(G)\) where \(\alpha\) is independence number (awareness).

Special values

Graph	\(\chi\)
Empty \(E_n\)	1
Bipartite, edges >0	2
Odd cycle \(C_{2k+1}\)	3
Even cycle	2
\(K_n\)	\(n\)
Tree \(n\ge 2\)	2

Theorem. \(G\) bipartite ⇔ \(\chi(G)\le 2\) (for graphs with at least one edge: \(=2\)).

Greedy coloring

Order vertices \(v_1,\ldots,v_n\); assign to each the smallest color not used by earlier neighbors.
Uses at most \(\Delta+1\) colors. Order matters for the number used (not always \(\chi\)).

Mycielski / high \(\chi\) triangle-free (awareness)

\(\chi\) can be arbitrarily large even with \(\omega=2\) (no triangles)—clique bound can be weak.

Planar graphs

\(G\) is planar if it can be drawn in the plane with no edge crossings (except at vertices).
Plane graph: a specific planar embedding.

Euler’s formula (connected plane graph): \(n-m+f=2\) where \(f\) is faces (including outer face).

Consequences for simple planar: \(m\le 3n-6\) for \(n\ge 3\); \(m\le 2n-4\) if triangle-free.
⇒ \(K_5\) nonplanar (\(10>9\)); \(K_{3,3}\) nonplanar (\(9>8\) for bipartite bound).

Four color theorem

Theorem (Appel–Haken 1976, computer-assisted; later simplifications). Every planar graph is 4-colorable: \(\chi(G)\le 4\) if \(G\) planar.

Five color theorem has a shorter classical proof.
Three color planar is NP-hard to decide in general.

Kuratowski / Wagner (awareness)

\(G\) planar ⇔ no subdivision of \(K_5\) or \(K_{3,3}\) (Kuratowski) ⇔ no \(K_5\) or \(K_{3,3}\) minor (Wagner).
Use: exhibit a \(K_{3,3}\) or \(K_5\) subdivision to prove nonplanar.

Dual graphs (lite)

For a plane graph, dual \(G^*\): face → vertex; edge between faces → edge in dual.
Face coloring of \(G\) ↔︎ vertex coloring of \(G^*\). Map coloring reduces to planar dual coloring.

Register allocation (story)

Compiler: variables/live ranges → vertices; edge if live ranges overlap (interfere).
Proper coloring → assign registers (colors) so interfering variables differ.
If \(\chi>\) number of registers, spill to memory (add vertices/edges heuristics).
Interference graphs are not always perfect/easy; SSA form helps structure.
Moral: graph coloring is the right model; exact \(\chi\) hard ⇒ heuristics (chordal graphs nice when SSA).

Greedy bound proof

Theorem. \(\chi(G)\le \Delta(G)+1\).
Proof. Order vertices arbitrarily. When coloring \(v\), it has at most \(\Delta\) neighbors, hence at most \(\Delta\) forbidden colors among those already colored; among \(\Delta+1\) colors, one remains free. \(\square\)

Brooks’ theorem (stated only): if \(G\) is connected, not complete, and not an odd cycle, then \(\chi\le \Delta\).

Euler ⇒ sparse ⇒ colorable (planar)

From \(m\le 3n-6\) (\(n\ge 3\) simple planar), average degree \(\frac{2m}{n}<6\), so \(\delta\le 5\). Every simple planar graph is \(5\)-degenerate ⇒ greedy coloring in a degeneracy order uses ≤6 colors. Five- and four-color theorems improve this; the edge bound is the engine of elementary planar coloring arguments.

Clique vs chromatic gap

\(\omega\le\chi\) always, but \(\chi-\omega\) can be large (Mycielski construction awareness). Odd cycles: \(\omega=2\), \(\chi=3\). Never assume equality outside perfect graphs (culture word).

Worked examples

Example 1 — \(\chi(K_4)=4\)

Planar (\(K_4\) planar!); needs 4 colors. So 4-color bound tight among planar graphs.

Example 2 — \(\chi(C_5)=3\)

Odd cycle; \(\omega=2<\chi\).

Example 3 — Bipartite

\(K_{2,3}\): \(\chi=2\); \(\omega=2\).

Example 4 — Greedy

Path \(a{-}b{-}c\): order \(a,c,b\) may use 2 colors; always ≤ \(\Delta+1=3\).

Example 5 — Clique bound

Any graph containing \(K_4\) has \(\chi\ge 4\).

Example 6 — \(K_5\) nonplanar

\(m=10>3\cdot5-6=9\).

Example 7 — \(K_{3,3}\) nonplanar

Bipartite planar \(m\le 2n-4=8\) but \(m=9\).

Example 8 — Planar max edges

Maximal planar triangulations: \(m=3n-6\), all faces triangles (n≥3).

Example 9 — Dual of tetrahedron

\(K_4\) plane embedding dual related to itself culture.

Example 10 — Register story micro

Variables \(a,b,c\): \(a\) overlaps \(b\), \(b\) overlaps \(c\), \(a\) not with \(c\): path interference ⇒ \(\chi=2\) registers enough.

Example 11 — Three mutual overlap

\(K_3\) interference ⇒ 3 registers.

Example 12 — Brooks

Connected \(\Delta=3\) not \(K_4\) not odd cycle ⇒ \(\chi\le 3\).

Example 13 — Map

Four countries all mutually adjacent impossible on plane without enclave tricks—related to \(K_5\) nonplanar.

Example 14 — \(\chi\) upper by degeneracy

Planar graphs are 5-degenerate ⇒ greedy ≤6; better theorems give 5, then 4.

Example 15 — Interval graphs

Interval/live-range pure interval graphs are perfect chordal—\(\chi=\omega\) poly-time—why register allocation on intervals is easier.

Example 16 — Greedy order matters

Bipartite \(K_{2,2}=C_4\) has \(\chi=2\), \(\Delta=2\). A bad ordering can still use only ≤3 colors by the theorem; on bipartite graphs some orders use exactly 2. Point: greedy number depends on order; \(\chi\) does not.

Example 17 — Exam schedule

Courses \(\{A,B,C,D\}\); conflicts \(AB,BC,CD,DA\) (a \(C_4\)): \(\chi=2\)—two slots suffice (schedule opposite courses together). Add diagonal \(AC\): now \(K_3\) plus, \(\chi=3\).

Example 18 — Euler check plane tree

Tree \(n\) vertices, \(m=n-1\), one face unbounded if drawn plane without cycles: \(n-(n-1)+1=2\). Euler OK.

Example 19 — Nonplanar with small \(\chi\)

\(K_{3,3}\): nonplanar, yet bipartite so \(\chi=2\). Planarity and chromatic number are related one way (planar ⇒ \(\chi\le 4\)) not the converse.

Example 20 — Degeneracy coloring idea

If every subgraph has a vertex of degree ≤\(k\), repeatedly remove such a vertex; color in reverse removal order with \(k+1\) colors. Planar ⇒ \(k=5\) elementary bound.

Exercises

Define proper coloring and \(\chi(G)\).
Prove \(\chi\ge\omega\).
Prove \(\chi(G)\le\Delta+1\) by greedy.
Compute \(\chi\) for \(C_6,C_7,K_{3,3},P_5\).
Show trees have \(\chi\le 2\).
Why is \(\chi(C_{2k+1})=3\)?
State four color theorem.
Prove \(K_5\) nonplanar via \(m\le 3n-6\).
Prove \(K_{3,3}\) nonplanar via bipartite planar bound.
Euler \(n-m+f=2\) for a plane tree (\(f=1\)? tree as plane: \(f=1\), \(n-(n-1)+1=2\) OK).
Greedy color a 6-vertex graph two different orders—compare colors used.
Register: build interference for 4 variables with given live overlaps; find \(\chi\).
True/false: planar ⇒ \(\chi\le 3\). (False: \(K_4\).)
True/false: \(\chi\le 4\) ⇒ planar. (False.)
Kuratowski: explain “subdivision” in one sentence.
Brooks statement for \(\Delta=2\).
Face coloring ⇔ dual vertex coloring.
CS: frequency assignment = coloring.
CS: exam scheduling = coloring.
Find \(\chi\) of Petersen (awareness 3 or 4?—Petersen \(\chi=3\)).
Challenge: prove five color theorem outline (optional).
Maximal planar \(n=6\): \(m=12\); \(\chi\)? (≤4, often 3 or 4).
Mycielski awareness: high \(\chi\) without triangles.
Show \(\chi(G\cup H)\) relations optional.
Portfolio: one nonplanar proof + one register micro-example.

CS connection

Register allocation via interference graphs.
Scheduling exams/rooms/frequencies.
Map/GIS and layout.
VLSI / circuit board planarity and crossings.
Resource conflict models broadly.

Common pitfalls

Pitfall	What to do instead
\(\chi=\Delta+1\) always	Greedy upper; can be smaller
\(\chi=\omega\) always	Odd cycles, Mycielski
Four color for all graphs	Planar only
\(m\le 3n-6\) for non-simple/nonplanar tests wrong	Hypotheses matter
Exact register \(\chi\) always computed	Heuristics in compilers

Checkpoint

\(\chi\) definition; \(\omega\le\chi\le\Delta+1\)
Bipartite \(\Leftrightarrow\chi\le 2\)
Four color statement
\(K_5\), \(K_{3,3}\) nonplanar arguments
Register allocation story
Exercises 1–15
Greedy coloring performed by hand

Two personal takeaways:

Selected mini-solutions

2; 3; 2; 2.
Not bipartite; odd cycle needs 3.
False (\(K_4\)).
False (\(K_5\) has \(\chi=5\) actually—bad; \(K_5\) χ=5; use \(K_5\) minor-free… \(\chi=4\) nonplanar examples exist e.g. \(K_{3,3}\) has χ=2 planar? \(K_{3,3}\) nonplanar χ=2. Nonplanar with χ=2: \(K_{3,3}\). So χ≤4 not ⇒ planar.
Petersen χ=3.

Deepening notes

Greedy coloring worst case

On bipartite graphs, bad order can use many colors temporarily? Actually bipartite \(\chi=2\) but greedy may use more than \(\chi\) though ≤\(\Delta+1\). Example: trees can greedy-use 2 if ordered carefully; still ≤3 for \(\Delta=2\).

Planarity quick kills

\(K_5\): \(m=10>9\).
\(K_{3,3}\): \(m=9>8=2n-4\).
Subdivision of either: also nonplanar (Kuratowski).

Register allocation micro-exercise (hand)

Live ranges as intervals on a timeline; interference = interval overlap graph = interval graph; color with \(\omega=\max\) depth of overlap.

Extra drills

D1. \(\chi\) of \(K_{2,2,2}\) (octahedral)—optional.
D2. Greedy two orders on \(P_4\).
D3. Prove \(\chi(G)\ge n/\alpha(G)\) sketch.
D4. Euler check for a plane \(K_4\) drawing: \(n-m+f=2\).
D5. Why \(K_{3,3}\) bipartite planar bound.
D6. Interference path of 4 vars—\(\chi\).
D7. Four color vs \(\chi(K_5)=5\) nonplanar.
D8. Map dual: countries adjacent → dual edge.

Flash

\(\omega\le\chi\le\Delta+1\); planar \(\Rightarrow\chi\le 4\); \(m\le 3n-6\); register = color interference graph.

Exam drill block

E1. Compute \(\chi\) for \(E_n,P_n,C_n,K_n,K_{m,n}\).
E2. Prove \(\chi\ge\omega\) and greedy \(\le\Delta+1\).
E3. Greedy color a 6-cycle two orders.
E4. \(K_5\) nonplanar via \(m\le 3n-6\).
E5. \(K_{3,3}\) nonplanar via \(m\le 2n-4\).
E6. Four color statement; show \(K_4\) planar needs 4.
E7. Register: 5 variables with given overlaps—build graph, \(\chi\).
E8. Face vs vertex coloring dual sentence.
E9. Brooks awareness for \(\Delta=3\).
E10. True/false: (i) planar ⇒ \(\chi\le 3\) (ii) \(\chi\le 4\) ⇒ planar (iii) bipartite ⇒ \(\chi\le 2\).

Mini solutions

E1. \(1\); \(2\) (\(n\ge2\)); \(2\) even / \(3\) odd; \(n\); \(2\) if edges.
E10. F; F; T.

Deep dive — Conflict models unified

Coloring is the canonical conflict graph tool:

Exams conflict → cannot share a slot.
Variables live simultaneously → cannot share a register.
Radios interfere → cannot share a frequency.
Map regions touch → cannot share a print color.

Build \(G\) first; \(\chi(G)\) is the resource count. Lower bound with \(\omega\) (find a clique of mutual conflicts); upper bound with greedy/degeneracy/structure (bipartite, planar, interval).

Synthesis

\(\omega\le\chi\le\Delta+1\) is the everyday sandwich. Bipartite graphs are exactly the graphs with \(\chi\le 2\) (edgeless \(\chi=1\)). Planar graphs satisfy \(\chi\le 4\) (four color) and \(m\le 3n-6\); \(K_5\) and \(K_{3,3}\) are the forbidden-structure gatekeepers. Register allocation is coloring of interference graphs—exact \(\chi\) hard, structure helps.

S1. Prove \(\chi\ge\omega\) and \(\chi\le\Delta+1\) in four sentences total.
S2. Compute \(\chi\) for \(C_8\), \(C_9\), \(K_{2,7}\), and a tree on 10 vertices.
S3. Show \(K_5\) and \(K_{3,3}\) nonplanar with the edge bounds.
S4. Build an interference graph for 5 variables with a specified overlap list; find \(\chi\) and a coloring.
S5. Why does “\(\chi\le 4\)” not imply planar? Give a counterexample class.

Tomorrow

Day 68 — Graphs in CS: dependency, call, CFG, social, routing, state-transition; modeling checklist; complexity culture.