Exercises: Graph Coloring, Planarity, and the Four Color Theorem

DataField.Dev

Exercises: Graph Coloring, Planarity, and the Four Color Theorem

These build from mechanical computation to full proofs, code, and modeling. Difficulty: ⭐ foundational, ⭐⭐ intermediate, ⭐⭐⭐ challenging. Worked solutions to the starred-with-a-dagger (†) and odd-numbered problems are in the appendix answers-to-selected.md; do them before you peek. Throughout, $\chi(G)$ is the chromatic number, $\omega(G)$ the clique number, $\Delta(G)$ the maximum degree, and $V, E, F$ are the vertex, edge, and face counts of a (plane) graph.

Part A — Warm-ups (⭐)

33.1 † For each graph, state $\chi$ and give the one-sentence reason: (a) $K_6$; (b) the even cycle $C_{10}$; (c) the odd cycle $C_9$; (d) a tree on 12 vertices; (e) the empty graph on 7 vertices (no edges).

33.2 Compute $\omega(G)$ and $\Delta(G)$, then state the bounds $\omega(G) \le \chi(G) \le \Delta(G)+1$ for the graph with vertices ${1,2,3,4,5}$ and edges ${1,2}, {2,3}, {1,3}, {3,4}, {4,5}$. What integer values are *not yet excluded* for $\chi(G)$?

33.3 † A connected simple planar graph has $V = 8$ vertices and is drawn in the plane with $F = 5$ faces. Use Euler's formula to find $E$.

33.4 For $K_{3,3}$: write down $V$ and $E$, and state which edge bound ($E \le 3V-6$ or $E \le 2V-4$) you must use to detect its non-planarity, and why the other one fails to catch it.

33.5 † Give a proper 3-coloring of the 5-cycle $C_5$ (vertices $0,1,2,3,4$, edges around the ring) by listing the color of each vertex. Then explain in one sentence why no 2-coloring exists.

33.6 State the Four Color Theorem precisely, then give a one-line reason why each of the following is not a consequence of it: (a) "$K_5$ is 4-colorable"; (b) "every map needs exactly four colors."

Part B — Compute it (⭐⭐)

33.7 † Build the interference graph for this straight-line code and find $\chi$ (the minimum number of registers). Show the live ranges, list the interference edges, give the largest clique, and exhibit an optimal register assignment.

1:  p = read()
2:  q = p + 1
3:  r = p + q
4:  s = q + r       # p dies after line 3
5:  return r + s

33.8 For the Petersen graph (a well-known 3-regular graph on 10 vertices; look up or draw it), state $\Delta$, give the upper bound $\chi \le \Delta+1$ it yields, and explain why this bound is not tight here (the Petersen graph's chromatic number is actually 3).

33.9 † A connected simple planar graph is triangle-free with $V = 11$ vertices. What is the maximum possible number of edges? Show the bound you used.

33.10 The complete bipartite graph $K_{2,5}$: compute $\chi$, $\omega$, and $\Delta$. Is $K_{2,5}$ planar? Justify with an edge bound or by drawing it.

33.11 † Five wireless access points must each be assigned a broadcast channel. Two that overlap cannot share a channel. The overlap pairs are: 1–2, 1–3, 2–3, 2–4, 3–4, 4–5. Find the minimum number of channels and exhibit an assignment. (Identify the structure: it is a graph you have seen.)

33.12 A plane drawing of a connected simple graph has every face bounded by exactly 5 edges (it is "pentagon-faced"). Using $\sum_f \deg(f) = 2E$ and Euler's formula, derive a relationship between $V$ and $E$. (This is the face-counting half of the dodecahedron's combinatorics.)

Part C — Prove it (⭐⭐ / ⭐⭐⭐)

33.13 † (Scaffolded — fill in the missing steps.) Prove the clique lower bound, Theorem 33.1: for every graph $G$, $\chi(G) \ge \omega(G)$. Fill the blanks.

Let $S$ be a largest clique in $G$, so $\lvert S \rvert = \underline{\hphantom{xxxx}}$, and let $c$ be any proper coloring.
Take any two distinct vertices $u, v \in S$. Because $S$ is a clique, $\{u,v\} \in \underline{\hphantom{xx}}$, and because $c$ is proper, $c(u) \underline{\hphantom{xx}} c(v)$.
Therefore $c$ assigns _____ colors to the vertices of $S$, so $c$ uses at least $\underline{\hphantom{xxxx}}$ colors.
Since $c$ was an arbitrary proper coloring, $\chi(G) \ge \underline{\hphantom{xxxx}}$. $\blacksquare$

33.14 Prove that for every graph $G$, $\chi(G) \le \Delta(G) + 1$, by giving the greedy argument in full (this is Theorem 33.2). Be explicit about why at least one color in $\{1, \dots, \Delta(G)+1\}$ is always free when you reach a vertex.

33.15 † Prove that $\chi(C_n) = 3$ for every odd $n \ge 3$. (Two parts: show 2 colors are not enough — use the odd-cycle / no-odd-cycle characterization, Theorem 33.3 — and show 3 colors suffice by exhibiting a coloring scheme.)

33.16 Prove the edge bound $E \le 3V - 6$ for a connected simple planar graph with $V \ge 3$, using the double-counting identity $\sum_f \deg(f) = 2E$ and Euler's formula. State clearly where "$V \ge 3$ and simple" is used (i.e., why every face has degree at least 3).

33.17 † (⭐⭐⭐, Deep Dive — the six-color theorem.) Prove that every planar graph is 6-colorable. Use this two-part scaffold: - Lemma. Every simple planar graph has a vertex of degree at most 5. (Prove it by contradiction: assume every vertex has degree $\ge 6$, sum the degrees using the handshaking lemma, and contradict the edge bound $E \le 3V - 6$.) - Main proof. Induct on the number of vertices. Remove a vertex $v$ of degree $\le 5$, 6-color the rest by the inductive hypothesis, then put $v$ back: it has at most 5 colored neighbors, so a 6th color is free.

33.18 (⭐⭐⭐, Deep Dive — the five-color theorem, structure only.) The five-color theorem (every planar graph is 5-colorable) refines Exercise 33.17. The induction is the same up to the last step: when you restore the degree-$\le 5$ vertex $v$ and all 5 colors are used by its neighbors, you must free one up using a Kempe chain argument. Without writing the full chain argument, explain (a) why the degree-$\le 5$ lemma alone gives only six colors, and (b) in one paragraph, the idea of a Kempe chain: a maximal connected subgraph using only two specified colors, and why recoloring it can release a color for $v$.

Part D — Implement it (⭐⭐)

Write Python for each. Do not run it on the grader's machine — hand-trace and include an # Expected output: comment, matching the book's convention. Assume the Graph API from Chapter 27 (g.vertices(), g.neighbors(v)), or use a plain adjacency dict.

33.19 † Implement greedy_coloring(adj, order) that takes an adjacency dict and a vertex order and returns a {vertex: color} dict using the greedy rule (smallest non-neighbor color, colors starting at 0). Trace it by hand on $C_5$ with order = [0,1,2,3,4] and report the number of colors used (1 + max(color.values())).

33.20 Write clique_lower_bound_3(adj) that returns True if the graph contains a triangle (a clique on 3 vertices) and False otherwise — a fast certificate that $\chi \ge 3$. (Check all triples, or all pairs of neighbors of each vertex.) Trace it on the exam graph from §33.1.

33.21 † Implement is_bipartite(adj, start) using BFS layer-parity (per §33.1's Connection): it should return True if the graph is 2-colorable from start's component and False the moment it finds an edge inside one layer. Trace it on the even cycle $C_4$ and the odd cycle $C_5$.

33.22 Implement passes_planar_edge_bound(V, E, triangle_free=False) that returns True if the edge count is consistent with planarity ($E \le 3V-6$, or $E \le 2V-4$ when triangle_free) for $V \ge 3$. Trace it on $K_5$ ($V=5,E=10$) and on $K_{3,3}$ ($V=6,E=9$, triangle-free). Note in a comment why a True result does not prove planarity.

Part E — Find the error (⭐⭐)

Each "proof" or claim below is wrong. State precisely which part fails and why.

33.23 † Claim: "$\chi(G) = \omega(G)$ for every graph $G$, because the largest clique is the only thing that forces colors." "Proof": Theorem 33.1 gives $\chi(G) \ge \omega(G)$; and you never need more colors than the size of the worst mutual conflict, so $\chi(G) \le \omega(G)$ as well; hence equality. — Find the flaw, and give the smallest concrete counterexample from the chapter.

33.24 Claim: "$K_{3,3}$ is planar because it satisfies the edge bound: $E = 9 \le 3V - 6 = 12$." Explain the logical error in this argument (what is the edge bound actually good for?), and state the correct bound that does detect $K_{3,3}$'s non-planarity.

33.25 † Claim: "The Four Color Theorem proves every graph can be colored with at most four colors." A student uses this to conclude their exam-scheduling graph (with $\chi = 6$) must really be 4-colorable and they made an arithmetic error. Identify the false premise and explain what the theorem actually claims, and about which graphs.

33.26 "Proof" that greedy coloring is optimal: "Greedy gives every vertex the smallest available color, so it is as economical as possible at each step; a sequence of locally optimal choices is globally optimal; therefore greedy uses $\chi(G)$ colors." Identify the false step in this reasoning and name the chapter's counterexample that refutes the conclusion.

Part F — Model it & Conjecture and test (⭐⭐⭐)

33.27 † (Model it.) A university must schedule final exams. There are 6 courses; the registrar gives you the list of student enrollments, from which you derive these "share at least one student" pairs: CS–MATH, CS–PHYS, MATH–PHYS, PHYS–CHEM, CHEM–BIO, BIO–ENG, ENG–CHEM. Translate this into a graph-coloring instance (state the vertices, edges, and what a color means), find the minimum number of exam periods, and exhibit a schedule. Then state, in coloring terms, what would have to be true for the schedule to fit into two periods.

33.28 (Model it — register allocation.) You are writing a register allocator for a machine with 3 registers. Given a function whose interference graph is the 5-cycle $C_5$, decide whether every value fits in a register or whether a spill is forced. Justify using $\chi(C_5)$, and identify which single value you might spill and why spilling one vertex makes the rest fit.

33.29 † (Conjecture and test, then prove.) Using greedy_coloring and chromatic_number from the Project Checkpoint, run both on the crown graph $\text{Crown}(n)$ (vertices $a_1,\dots,a_n, b_1,\dots,b_n$; edge $a_i b_j$ iff $i \ne j$) for $n = 2, 3, 4, 5$, using the adversarial order $a_1, b_1, a_2, b_2, \dots$. Tabulate (greedy color count) vs. ($\chi$). Conjecture a formula for each as a function of $n$, then prove both: that $\chi(\text{Crown}(n)) = 2$, and that greedy on the adversarial order uses $n$ colors. (Do not execute — hand-trace small $n$ and reason.)

33.30 (Conjecture and test.) For $n = 3, 4, 5, 6$, build $K_n$ and use the edge bound to test whether it could be planar ($E \le 3V - 6$?). Tabulate $V$, $E = \binom{n}{2}$, $3V-6$, and the verdict. At which $n$ does $K_n$ first fail the bound? Conjecture and justify a general statement: "for $n \ge \underline{\hphantom{x}}$, $K_n$ is non-planar," and prove your threshold using the bound.

Part G — Interleaved & Deep Dive

Mixing techniques from earlier chapters keeps them sharp.

33.31 † (Ch. 6 + 33.) Exercise 33.17 used induction on the number of vertices. Write the inductive hypothesis explicitly for the claim "every planar graph on $n$ vertices is 6-colorable," identify the base case, and state the one structural lemma (about a low-degree vertex) that powers the inductive step. (You do not need to re-prove it — just lay out the induction skeleton, as in Chapter 6.)

33.32 (Ch. 27 + 33.) The handshaking lemma (Ch. 27) says $\sum_v \deg(v) = 2E$. The planar edge bound used a face analogue $\sum_f \deg(f) = 2E$. State the single double-counting principle behind both, and explain in one sentence what is being counted "from two sides" in each case.

33.33 † (Ch. 30 + 33.) Chapter 30 contrasted an easy graph problem (Euler paths, polynomial) with a hard one (Hamilton paths / TSP). Where does deciding 3-colorability fall on that easy/hard boundary, and where does deciding 2-colorability fall? Explain why the two differ, citing the relevant algorithm for the easy case.

33.34 (Ch. 31 + 33.) A tree (Ch. 31) on $n \ge 2$ vertices has exactly $n - 1$ edges and no cycles. Use both facts to give two independent proofs that every such tree has $\chi = 2$: (a) via the "no odd cycle" characterization (Theorem 33.3); (b) via Euler's formula reasoning about faces (how many faces does a tree's plane drawing have, and what does that say?).

33.35 (Deep Dive — anchor: social networks.) Recall this chapter's social-network anchor: a color class of a proper coloring is an independent set (a set of mutual non-friends). Suppose a friendship graph $G$ has $\chi(G) = k$. Prove that $G$'s vertices can be partitioned into $k$ independent sets, and conversely that a partition into $k$ independent sets yields a proper $k$-coloring. Then explain, in one paragraph, what $\chi(G)$ tells a community organizer who wants to split a social network into the fewest groups of mutual strangers — and contrast this with the opposite goal (finding one large tightly-knit group, i.e. a large clique) that the capstone's analyzer (Ch. 39, Track B) also supports.

Solutions to † and odd-numbered exercises: see appendices/answers-to-selected.md. For each proof, the rubric rewards: precise definitions, a correctly identified lower/upper bound or base case, explicit use of the relevant theorem (clique bound, greedy bound, Euler's formula, the bipartite characterization), and a clean conclusion. For modeling problems, state vertices, edges, and the meaning of a color before computing.