Self-Assessment Quiz: Graph Coloring, Planarity, and the Four Color Theorem

Twenty questions to check your understanding. Answer before opening the key. Aim for 16+.

Question 1

A proper coloring of $G = (V,E)$ with $k$ colors is a function $c\colon V \to \{1,\dots,k\}$ such that:

A) $c(u) = c(v)$ for every edge $\{u,v\}$ B) $c(u) \neq c(v)$ for every edge $\{u,v\}$ C) every color in $\{1,\dots,k\}$ is used at least once D) non-adjacent vertices get the same color

Question 2

The chromatic number $\chi(G)$ is:

A) the number of edges in $G$ B) the maximum degree of $G$ C) the smallest $k$ for which a proper $k$-coloring exists D) the size of the largest clique

Question 3

For the complete graph $K_n$, the chromatic number is:

A) $2$ B) $n - 1$ C) $n$ D) $\lceil n/2 \rceil$

Question 4

$\chi(C_n)$ for a cycle on $n$ vertices is:

A) always $2$ B) always $3$ C) $2$ if $n$ is even, $3$ if $n$ is odd D) $3$ if $n$ is even, $2$ if $n$ is odd

Question 5

Which pair of bounds always holds for every graph $G$?

A) $\Delta(G) \le \chi(G) \le \omega(G)$ B) $\omega(G) \le \chi(G) \le \Delta(G) + 1$ C) $\chi(G) \le \omega(G) \le \Delta(G)$ D) $\omega(G) + 1 \le \chi(G) \le \Delta(G)$

Question 6 (True/False, justify)

True or false: $\chi(G) = \omega(G)$ for every graph $G$. Justify in one sentence (name a counterexample if false).

Question 7

A graph with at least one edge is 2-colorable if and only if it is:

A) a tree B) bipartite (equivalently, has no odd cycle) C) planar D) complete

Question 8

Which standard graph is triangle-free yet has $\chi = 3$ (showing the clique bound is not tight)?

A) $K_4$ B) $C_4$ C) $C_5$ D) a path on 5 vertices

Question 9

In a compiler's interference graph, an edge between two values means:

A) the two values are never used B) the two values are simultaneously live (cannot share a register) C) the two values are always equal D) the two values are stored in memory

Question 10

In an interference graph, the chromatic number corresponds to:

A) the number of variables in the program B) the number of lines of code C) the minimum number of registers needed for a spill-free allocation D) the number of function calls

Question 11

Euler's formula for a connected plane graph states:

A) $V + E + F = 2$ B) $V - E + F = 2$ C) $V - E - F = 0$ D) $E = 3V - 6$

Question 12

The edge bound $E \le 3V - 6$ (for a connected simple planar graph, $V \ge 3$) is:

A) sufficient for planarity (passing it proves planar) B) necessary for planarity (failing it proves non-planar) C) both necessary and sufficient D) neither — it is unrelated to planarity

Question 13

Which proves $K_5$ is non-planar most directly?

A) $K_5$ is bipartite B) $E = 10 > 9 = 3V - 6$ C) $K_5$ has an Euler circuit D) $K_5$ is a tree

Question 14

To detect that $K_{3,3}$ is non-planar via an edge bound, you must use:

A) $E \le 3V - 6$ (it catches $K_{3,3}$) B) $E \le 2V - 4$, the triangle-free bound, because $K_{3,3}$ is bipartite C) Euler's formula directly with no inequality D) the clique bound $\chi \ge \omega$

Question 15

Kuratowski's theorem says a graph is planar if and only if it contains no subgraph that is a subdivision of:

A) $K_4$ or $C_5$ B) any cycle C) $K_5$ or $K_{3,3}$ D) a tree

Question 16 (True/False, justify)

True or false: The Four Color Theorem says every graph is 4-colorable. Justify in one sentence.

Question 17

What made the 1976 Appel–Haken proof of the Four Color Theorem philosophically controversial?

A) it used a false lemma B) it was the first major theorem whose proof required a computer to check a huge case analysis no human could verify by hand C) it disproved Euler's formula D) it was never published

Question 18

Greedy coloring with vertices in a fixed order:

A) always uses exactly $\chi(G)$ colors B) always produces a proper coloring but is not guaranteed minimal C) may produce an improper coloring D) requires the graph to be planar

Question 19 (Short answer)

The crown graph (bipartite, so $\chi = 2$) can fool greedy into using $n$ colors. In one sentence, explain what causes greedy's bad result and what a good vertex order would do.

Question 20 (Short answer)

State, in one sentence each, the two facts the chapter gives about a planar graph's chromatic number: the guaranteed upper bound (the named theorem) and the easy lower-bound example showing that bound can be reached.

Answer Key

Q Ans Note
1 B The single rule: adjacent vertices get different colors.
2 C Smallest number of colors admitting a proper coloring.
3 C All $n$ vertices are pairwise adjacent, so $\chi(K_n)=n$.
4 C Even cycles alternate two colors; odd cycles collide on wrap-around and need three.
5 B Clique forces colors below; greedy gives $\Delta+1$ above.
6 False $C_5$ is triangle-free ($\omega=2$) yet $\chi=3$; cliques are not the only thing that forces colors.
7 B 2-colorable $\iff$ bipartite $\iff$ no odd cycle (Theorem 33.3).
8 C The 5-cycle: no triangle, but an odd cycle, so $\chi = 3$.
9 B Interference = simultaneously live = cannot reuse the same register.
10 C $\chi$ = minimum registers for a spill-free allocation.
11 B $V - E + F = 2$ for connected plane graphs.
12 B Necessary, not sufficient: failing it proves non-planar; passing it proves nothing.
13 B $K_5$ has $E=10$ but planarity needs $E \le 9$.
14 B $K_{3,3}$ satisfies $E \le 3V-6$; only the triangle-free bound $E \le 2V-4=8 < 9$ catches it.
15 C $K_5$ and $K_{3,3}$ are the only two obstructions (up to subdivision).
16 False It applies only to planar graphs; $K_5$ needs 5 colors, $K_{100}$ needs 100.
17 B First major theorem checked by computer case analysis, unsurveyable by a human.
18 B Always proper, never more than $\Delta+1$ colors, but not necessarily minimal.
19 — The interleaved order forces each pair to a new color; a good order (all $a$'s, then all $b$'s) finds the optimal 2-coloring.
20 — Upper bound: the Four Color Theorem, $\chi \le 4$ for planar graphs. Lower-bound example: $K_4$ drawn as a map has $\chi = 4$, so 4 can be necessary.

Topics to review by question

Questions Topic
1–2 Definitions: proper coloring, chromatic number (§33.1)
3–4, 8 Chromatic numbers of standard graphs ($K_n$, $C_n$, triangle-free) (§33.1)
5–6 The clique and degree bounds; why $\chi \ne \omega$ in general (§33.1)
7 2-colorability = bipartite = no odd cycle (§33.1, Theorem 33.3)
9–10 Register allocation / interference graphs (§33.2)
11 Euler's formula (§33.3)
12–14 Edge bounds and detecting non-planarity (§33.3)
15 Kuratowski's theorem (§33.4)
16–17 The Four Color Theorem: statement and the computer-proof controversy (§33.5)
18–19 Greedy coloring: properness, $\Delta+1$ bound, order dependence, worst case (§33.6)
20 Synthesis: planar chromatic bound and its tightness (§33.5)