Chapter 33: Graph Coloring, Planarity, and the Four Color Theorem

"A planar map is four colorable." — Kenneth Appel and Wolfgang Haken, announcing the 1976 proof

Overview

Here is a problem you will eventually have to solve, in some disguise, no matter what kind of software you build. You have a set of things, and some pairs of them conflict — they cannot share a resource. Final exams that share a student cannot run in the same time slot. Two variables that are both "live" at the same instant cannot live in the same CPU register. Two cell towers that overlap cannot broadcast on the same frequency. Two jobs that touch the same file cannot run concurrently. In every case the question is identical: what is the fewest number of resources (slots, registers, frequencies, locks) that lets everything run without a conflict?

Strip away the words and every one of these is the same mathematical object. Make a graph: one vertex per thing, one edge between every pair that conflicts. A "resource assignment with no conflict" is then exactly a way of labeling the vertices so that no edge has both endpoints with the same label. The labels are traditionally called colors, and the minimum number of colors you need is the single most important parameter in this chapter. A compiler's register allocator, the algorithm that decides which of your program's values live in fast registers and which get spilled to slow memory, is literally a graph-coloring engine. When you understand this chapter, you understand the core of that allocator.

Coloring will also pull us into one of the most famous stories in all of mathematics. If your graph happens to be a map — countries that share a border are adjacent — how many colors do you need so neighboring countries differ? The answer, four, took 124 years to prove and, when the proof finally arrived in 1976, it broke with tradition so sharply that mathematicians argued about whether it counted as a proof at all. It was the first major theorem whose proof no human could fully check by hand. That story is worth knowing not for trivia but because it forces a real question: what is a proof, once a computer is part of it?

In this chapter, you will learn to:

• Model conflict problems as graphs and reduce them to coloring.
• Compute the chromatic number for small graphs and bound it for large ones.
• Decide whether a graph can be drawn in the plane without crossings, and prove specific graphs cannot.
• State Euler's formula and Kuratowski's theorem and apply each to real reasoning.
• State the Four Color Theorem precisely and explain the controversy its proof created.
• Implement greedy coloring, analyze it, and build the input that defeats it.

Learning Paths

🏃 Fast Track: If you only need the engineering payoff, read 33.1 (definitions), 33.2 (applications — register allocation especially), and 33.6 (greedy coloring and its limits). Do the ⭐⭐/⭐⭐⭐ exercises on those. You can treat planarity as cultural background.

📖 Standard Path: Read in order. Work every 🔄 Check Your Understanding before moving on. In 33.3, prove Euler's formula yourself before reading our proof — the strategy hint is enough to get you started.

🔬 Deep Dive: After the chapter, prove that every planar graph is 6-colorable, then upgrade your argument to 5-colorable (the five-color theorem, which is humanly provable). Both are in the exercises, Part D. Then read one of the further-reading accounts of the Appel–Haken proof and form your own opinion on the computer-proof question.

33.1 Graph coloring and the chromatic number

Let's start with the smallest interesting instance of the exam-scheduling problem. Five courses — call them A, B, C, D, E — are giving final exams. Some pairs share at least one enrolled student, so their exams cannot be at the same time:

• A conflicts with B and C.
• B conflicts with A, C, and D.
• C conflicts with A, B, and D.
• D conflicts with B, C, and E.
• E conflicts with D.

Model it as a graph $G$: a vertex for each course, an edge for each conflict. We want to assign each course a time slot so that conflicting courses get different slots, using as few slots as possible.

Try it by hand. Give A slot 1. B conflicts with A, so B needs slot 2. C conflicts with both A and B, so C needs slot 3. D conflicts with B and C (slots 2 and 3) but not A, so D can reuse slot 1. E conflicts only with D (slot 1), so E can take slot 2. Three slots suffice: $\{A,D\} \to 1$, $\{B,E\} \to 2$, $\{C\} \to 3$. And we cannot do better, because A, B, C all conflict with each other — three courses, no two of which can share — so at least three slots are forced.

That is the entire idea. Let us make it precise.

Definition (proper coloring). A proper coloring of a graph $G = (V,E)$ with $k$ colors is a function $c\colon V \to \{1, 2, \dots, k\}$ such that for every edge $\{u,v\} \in E$, $c(u) \neq c(v)$. A graph is $k$-colorable if a proper coloring with $k$ colors exists. The chromatic number of $G$, written $\chi(G)$, is the smallest $k$ for which $G$ is $k$-colorable.

The colors are just labels $1,2,\dots,k$ (or red/green/blue, or time slots, or registers — whatever the application calls them). The single rule is the edge rule: adjacent vertices get different colors. There is no requirement that you use all $k$ colors, and no requirement about non-adjacent vertices — they may share a color or not, as convenient.

For our exam graph, we exhibited a proper 3-coloring and argued no 2-coloring exists, so $\chi(G) = 3$.

💡 Intuition: Think of $\chi(G)$ as a measure of how "tangled" the conflicts are. A graph with no edges has $\chi = 1$ (everything shares one color). The more densely things conflict, the more colors you are forced to use. The chromatic number is the price of the conflict structure, measured in resources.

Two immediate lower bounds

Computing $\chi(G)$ exactly is hard in general (we'll return to how hard at the end of the chapter and again in Chapter 37). But two lower bounds are easy and constantly useful.

The first comes straight from our exam example. A clique is a set of vertices that are pairwise adjacent — every two of them share an edge. (The complete graph $K_n$, introduced in Chapter 27, is a clique on $n$ vertices.) If $G$ contains a clique on $\omega$ vertices, those $\omega$ vertices all conflict with each other, so they need $\omega$ distinct colors.

Definition (clique number). The clique number of $G$, written $\omega(G)$, is the number of vertices in the largest clique in $G$.

Theorem 33.1 (clique lower bound). For every graph $G$, $\chi(G) \ge \omega(G)$.

The strategy first. This is almost a definition-chase. A clique on $\omega(G)$ vertices is a set of mutually adjacent vertices; the edge rule forces them to be pairwise different colors; so any proper coloring already spends at least $\omega(G)$ colors on that one clique alone.

Proof. Let $S$ be a largest clique in $G$, so $\lvert S \rvert = \omega(G)$, and let $c$ be any proper coloring of $G$. Take any two distinct vertices $u, v \in S$. Because $S$ is a clique, $\{u,v\} \in E$, and because $c$ is proper, $c(u) \neq c(v)$. So $c$ assigns pairwise distinct colors to the vertices of $S$, meaning $c$ uses at least $\lvert S \rvert = \omega(G)$ colors. As $c$ was an arbitrary proper coloring, every proper coloring uses at least $\omega(G)$ colors, so $\chi(G) \ge \omega(G)$. $\blacksquare$

The second easy fact is an upper bound from vertex degrees. Recall $\deg(v)$ is the number of neighbors of $v$ (Chapter 27). Let $\Delta(G) = \max_v \deg(v)$ be the maximum degree.

Theorem 33.2 (greedy upper bound). For every graph $G$, $\chi(G) \le \Delta(G) + 1$.

The strategy first. Color the vertices one at a time, in any order, always giving the current vertex the smallest color not already used by its neighbors. When we reach a vertex $v$, it has at most $\Delta(G)$ neighbors, so at most $\Delta(G)$ colors are forbidden; among the colors $1, 2, \dots, \Delta(G)+1$ there are $\Delta(G)+1$ choices, so at least one is free. We never run out. This constructive proof is also an algorithm — it is exactly the greedy coloring of section 33.6.

Proof. Order the vertices $v_1, v_2, \dots, v_n$ arbitrarily. Color them in this order, assigning to each $v_i$ the smallest color in $\{1, 2, \dots, \Delta(G)+1\}$ that none of its already-colored neighbors uses. We claim this never fails. When we color $v_i$, the colors we must avoid are exactly those of its colored neighbors, and $v_i$ has at most $\deg(v_i) \le \Delta(G)$ neighbors total. So at most $\Delta(G)$ colors are forbidden, leaving at least one of the $\Delta(G)+1$ available colors free. Thus every vertex receives a color, no two adjacent vertices share one (we explicitly avoided neighbor colors), and the coloring uses at most $\Delta(G)+1$ colors. Hence $\chi(G) \le \Delta(G)+1$. $\blacksquare$

Putting the two together, $\omega(G) \le \chi(G) \le \Delta(G) + 1$. These bounds can be far apart, but they pin $\chi$ down for many graphs at once.

⚠️ Common Pitfall: $\chi(G) \ge \omega(G)$ is a lower bound, not an equality. It is tempting to assume the chromatic number always equals the largest clique — "you only need as many colors as your worst mutual conflict." That is false. There exist triangle-free graphs (clique number 2, no three mutual conflicts at all) that nonetheless need arbitrarily many colors. The cleanest small example is the 5-cycle $C_5$: it has no triangle, so $\omega(C_5) = 2$, yet $\chi(C_5) = 3$ (try to 2-color a pentagon and you will fail on the last edge). Cliques force colors, but they are not the only thing that forces colors.

Worked example: chromatic numbers of standard graphs

Knowing $\chi$ for a few standard families lets you bound new graphs by comparison.

• Complete graph $K_n$: every pair is adjacent, so all $n$ vertices need different colors: $\chi(K_n) = n$. (Here the clique bound is tight: $\omega = \chi = n$.)
• Cycle $C_n$: if $n$ is even, alternate two colors around the ring: $\chi(C_n) = 2$. If $n$ is odd, the alternation collides when it wraps around, and you need a third color: $\chi(C_n) = 3$. So $\chi(C_n) = 2$ for even $n \ge 4$ and $3$ for odd $n \ge 3$.
• Bipartite graphs: a graph is bipartite (Chapter 27) exactly when its vertices split into two sides with all edges crossing between them. Color one side 1 and the other 2 and no edge is monochromatic, so every bipartite graph with at least one edge has $\chi = 2$. The converse holds too, giving a clean characterization we prove below.
• Trees: a tree (Chapter 31) is bipartite — it has no cycles at all, let alone odd ones — so every tree with at least one edge has $\chi = 2$.

Theorem 33.3 (2-colorability = bipartite). A graph $G$ with at least one edge satisfies $\chi(G) = 2$ if and only if $G$ is bipartite, which holds if and only if $G$ has no cycle of odd length.

The strategy first. "$\chi(G)=2$ iff bipartite" is almost a restatement: a 2-coloring is a partition into two color classes, and properness says no edge stays inside a class — which is the definition of bipartite. The interesting equivalence is "bipartite iff no odd cycle." Forward: an odd cycle can't be 2-colored, so it can't sit inside a bipartite graph. Backward: if there are no odd cycles, we build a 2-coloring by walking the graph and coloring each vertex by the parity of its distance from a start vertex; oddless-ness is exactly what guarantees no edge joins two vertices of equal parity.

Proof. First, $\chi(G) = 2$ iff $G$ is bipartite. A proper 2-coloring $c\colon V \to \{1,2\}$ partitions $V$ into $X = c^{-1}(1)$ and $Y = c^{-1}(2)$; properness means every edge has endpoints of different colors, i.e. one endpoint in $X$ and one in $Y$ — exactly the bipartite condition. Conversely a bipartition $(X,Y)$ gives the 2-coloring "1 on $X$, 2 on $Y$," which is proper. (Since $G$ has an edge, one color alone fails, so the minimum is exactly 2.)

Now, bipartite iff no odd cycle. ($\Rightarrow$) Suppose $G$ is bipartite with sides $X, Y$, and walk around any cycle $v_0, v_1, \dots, v_\ell = v_0$. Each step crosses from one side to the other, so the side alternates $X, Y, X, Y, \dots$ To return to the starting side after $\ell$ steps, $\ell$ must be even. Hence every cycle has even length; there are no odd cycles.

($\Leftarrow$) Suppose $G$ has no odd cycle. We may assume $G$ is connected (otherwise color each component separately). Pick any vertex $r$ and let $d(v)$ be the length of a shortest path from $r$ to $v$. Color $v$ with $1$ if $d(v)$ is even and $2$ if $d(v)$ is odd. We claim this 2-coloring is proper. Suppose, for contradiction, some edge $\{u,v\}$ had $d(u)$ and $d(v)$ of the same parity. The shortest path from $r$ to $u$ (length $d(u)$), the edge $\{u,v\}$, and the shortest path from $v$ back to $r$ (length $d(v)$) together form a closed walk of length $d(u) + 1 + d(v)$, which is odd since $d(u)+d(v)$ is even. A closed walk of odd length always contains an odd cycle (an even-length closed walk can be decomposed into cycles, all of which cannot be even if the total is odd). This contradicts our assumption of no odd cycle. So every edge joins vertices of opposite parity, the coloring is proper, and $G$ is bipartite. $\blacksquare$

🔗 Connection. This theorem is secretly an algorithm. Run breadth-first search (Chapter 28) from any vertex; BFS computes exactly the distances $d(v)$ as it explores in layers. Coloring by the parity of the BFS layer 2-colors the graph if it is bipartite, and the moment BFS finds an edge within a layer, you have located an odd cycle and proven the graph is not bipartite. So "is this graph bipartite?" is answerable in linear time — a rare gift, since deciding $k$-colorability for $k \ge 3$ is NP-complete (Chapter 37).

🔄 Check Your Understanding 1. A graph has a triangle and maximum degree 4. What can you conclude about $\chi(G)$ from the two bounds in this section? 2. Why is every tree 2-colorable? Give the one-sentence reason. 3. Is $\chi(C_7) = 2$ or $3$? Why?

Answers

1. The triangle is a clique on 3 vertices, so $\omega(G) \ge 3$ gives $\chi(G) \ge 3$; the degree bound gives $\chi(G) \le \Delta+1 = 5$. So $3 \le \chi(G) \le 5$.
2. A tree has no cycles, hence no odd cycles, so by Theorem 33.3 it is bipartite and (having an edge) 2-colorable.
3. $\chi(C_7) = 3$: 7 is odd, and odd cycles need three colors because two-coloring an odd ring forces a collision where it wraps around.

33.2 Applications: scheduling, register allocation, and maps

The reason coloring is in a CS curriculum, and not just a recreational-math curriculum, is that resource-conflict problems are everywhere, and they are all this one problem wearing different clothes. The recipe is always the same:

The coloring modeling recipe. 1. Vertices = the things that need a resource. 2. Edges = the pairs that cannot share a resource (the conflicts). 3. Colors = the available resources (slots, registers, frequencies, channels). 4. A proper coloring = a conflict-free assignment; $\chi(G)$ = the minimum number of resources needed.

Exam and shift scheduling

We already did exam scheduling: vertices are exams, edges join exams that share a student, colors are time slots, and $\chi(G)$ is the minimum number of exam periods. The same model schedules meetings into rooms (edge = two meetings overlap in time, color = room), assigns referees to games, and lays out shifts. Whenever the question is "group these so conflicting members are separated, using fewest groups," it is graph coloring.

🔗 Connection (anchor: social networks). This chapter's anchor is the social-network graph we have been building since Chapter 27. Coloring gives us a new lens on it. Suppose you are scheduling a series of discussion panels drawn from a community, and two people who are friends (adjacent in the social graph) should be split across different panels to mix the room. The colors are panels; $\chi$ of the friendship graph is the fewest panels that fully separates every friend pair. Conversely, a color class — a set of vertices all sharing one color — is by definition an independent set: no two of them are adjacent, i.e. a group of mutual strangers. Reading coloring "the other way," it partitions a network into the fewest groups of mutual non-friends. We will return to the dual view — finding tightly-knit groups rather than separating them — when the capstone (Chapter 39, Track B) builds a full social-network analyzer.

Register allocation: coloring inside your compiler

This is the application that makes coloring indispensable to systems programmers. A CPU has a small fixed number of fast registers (say 16 on x86-64). A function in your program has many variables (more precisely, values or temporaries). The compiler must decide which values live in registers and which "spill" to slow main memory. Two values can share one register if and only if they are never needed at the same time.

Make the interference graph: one vertex per value; an edge between two values that are simultaneously live (both will still be read later) at some point in the program. A register assignment with no clash is exactly a proper coloring of this graph, with colors = registers. If the interference graph is $k$-colorable for $k$ = number of registers, every value fits in a register. If not — if $\chi > k$ — some values must spill to memory, and the compiler picks which using exactly the structure of the graph.

💡 Intuition: "Two values interfere" means "their lifetimes overlap, so they can't reuse the same storage." That is identical to "two exams share a student, so they can't reuse the same time slot." Register allocation is exam scheduling where exams are program values and time slots are CPU registers. This is not an analogy bolted on after the fact — it is the same theorem, and real compilers (GCC, LLVM) implement graph-coloring register allocators built on exactly the algorithm in section 33.6.

Here is a tiny worked instance. Consider this straight-line code and the live ranges of its values:

1:  a = read()         # a live from here
2:  b = a + 1          # b live from here; a still live (used line 3)
3:  c = a + b          # a dies after this; c live from here
4:  d = b + c          # b dies; c dies after line 5; d live
5:  e = c + d          # c dies; d dies after line 6; e live
6:  return d + e

At line 3, values a, b are both live (and c is being created); after line 3, a is dead. At line 4, b, c are live; d is created. The interference edges (values live at the same time) are: $\{a,b\}, \{a,c\}, \{b,c\}, \{b,d\}, \{c,d\}, \{c,e\}, \{d,e\}$. The largest clique is $\{a,b,c\}$ (all live around line 3), so $\omega = 3$ and we need at least 3 registers. A proper 3-coloring exists — e.g. registers $a\!=\!R1, b\!=\!R2, c\!=\!R3, d\!=\!R1, e\!=\!R2$ — so 3 registers suffice and $\chi = 3$. With only 2 registers, one value would spill.

🔗 Connection. That clique $\{a, b, c\}$ is the "register pressure" at its peak: three values alive at once means three registers, no matter how clever the allocator. The clique lower bound from Theorem 33.1 is precisely a lower bound on register pressure. When a compiler reports it had to spill, it is reporting that $\chi(G) >$ (registers), and the clique bound is the quickest certificate of why.

Map coloring

The original application — and the source of the Four Color Theorem — is coloring maps. Given a political map, color the regions so that any two regions sharing a border segment get different colors. Model it as a graph: one vertex per region, an edge between regions that share a border (touching at a single point doesn't count). The minimum number of colors is $\chi$ of that graph. The deep fact, which we build toward across the next three sections, is that every map graph — because it can be drawn in the plane without crossings — needs at most four colors. We turn now to the property that makes a graph a "map": planarity.

🔄 Check Your Understanding 1. In an interference graph, what real-world quantity does the chromatic number measure? What does a clique correspond to? 2. You model exam scheduling and find $\chi(G) = 5$, but the university only has 4 exam periods. In coloring terms, what must happen? 3. Why does "two regions touching at a single corner point" not create an edge in a map graph?

Answers

1. $\chi$ = the minimum number of registers needed for a spill-free allocation; a clique = a set of values all simultaneously live (peak register pressure).
2. The graph is not 4-colorable ($\chi > 4$), so no conflict-free schedule into 4 periods exists — at least one student will have a conflict, or an exam must be moved/split. There is no way around it; it is a hard constraint of the conflict structure.
3. Because two regions meeting only at a point can always get the same color without any border looking ambiguous — the convention is that adjacency requires a shared border of positive length. (Otherwise four regions meeting at one corner could force arbitrarily many colors, and the four-color result would be false.)

33.3 Planar graphs and Euler's formula

A graph is planar if you can draw it in the plane with the vertices as points and the edges as curves that meet only at their shared endpoints — no two edges cross. The same abstract graph can have a tangled drawing with crossings and a clean drawing with none; what matters is whether some crossing-free drawing exists.

Look at $K_4$, the complete graph on four vertices. Drawn as a square with both diagonals, the diagonals cross. But redraw it with one vertex inside a triangle of the other three, and the crossing vanishes — $K_4$ is planar. Contrast $K_5$: no matter how you arrange five mutually-connected vertices, you cannot avoid a crossing (we'll prove it). Planarity is a real, sometimes surprising, property.

Definition (planar graph, plane graph, face). A graph is planar if it can be drawn in the plane with no edge crossings. A particular crossing-free drawing is called a plane graph (a planar graph plus a chosen drawing). A plane graph divides the plane into connected regions called faces; exactly one of them is the unbounded outer face.

Why does a programmer care? Planar graphs are the graphs of things laid out in physical 2-D space: circuit boards where wires must not cross (or must cross only on separate layers), road maps, VLSI chip layouts, and any planar mesh in graphics. Planar graphs are also algorithmically friendlier than general graphs — many problems that are hard in general become tractable on planar inputs. And the route to the Four Color Theorem runs straight through one beautiful counting identity.

Euler's formula

Draw any connected plane graph and count three things: the number of vertices $V$, edges $E$, and faces $F$ (including the outer face). A tetrahedron-style drawing of $K_4$ has $V=4$, $E=6$, and $F=4$ (three inner triangles plus the outside). Then $V - E + F = 4 - 6 + 4 = 2$. Draw a single triangle: $V=3, E=3, F=2$, and $3 - 3 + 2 = 2$. Draw a path of three vertices: $V=3, E=2, F=1$, and $3-2+1 = 2$. Every time, the alternating sum is $2$. This is no accident.

Theorem 33.4 (Euler's formula). For every connected plane graph with $V$ vertices, $E$ edges, and $F$ faces, $$V - E + F = 2.$$

The strategy first. We prove it by induction — but on what? The slick choice is induction on the number of edges. The base case is a connected graph with the fewest edges a connected graph on its vertices can have: a tree, which has $V-1$ edges and only the single outer face. For the inductive step we look at a connected plane graph with one more edge than needed for a tree, which means it contains a cycle; removing one edge of a cycle keeps it connected but merges two faces into one, dropping both $E$ and $F$ by exactly 1 — so the alternating sum $V - E + F$ is unchanged. Induction does the rest. The key geometric fact powering the step is: an edge that lies on a cycle borders two different faces, and deleting it merges them.

Proof. We induct on the number of edges $E$ of a connected plane graph on a fixed vertex set of size $V \ge 1$.

Base case. A connected graph on $V$ vertices has at least $V-1$ edges; the minimum, $E = V-1$, is achieved exactly by trees (Chapter 31). A tree, drawn in the plane, has no cycles, so it encloses no region: there is a single face, the outer one, giving $F = 1$. Then $V - E + F = V - (V-1) + 1 = 2$. So the formula holds for every connected plane graph with $E = V-1$.

Inductive step. Fix $m \ge V$ and assume the formula holds for every connected plane graph with $m - 1$ edges. Let $H$ be a connected plane graph with $V$ vertices and $E = m \ge V$ edges. Since $H$ has more than $V-1$ edges, it is not a tree, so it contains a cycle; let $e$ be an edge on that cycle. Because $e$ lies on a cycle, it is not a bridge, so deleting it leaves a connected plane graph $H' = H - e$ with $V$ vertices and $m - 1$ edges. Geometrically, $e$ separated two distinct faces of $H$ (a cycle edge always has a different face on each side); deleting $e$ merges those two faces into one, so $H'$ has exactly one fewer face: $F' = F - 1$. By the inductive hypothesis applied to $H'$, $$V - (m-1) + (F-1) = 2.$$ Rearranging, $V - m + F = 2$, which is Euler's formula for $H$. By induction, $V - E + F = 2$ for every connected plane graph. $\blacksquare$

🔗 Connection. Euler's formula is the same $V - E + F = 2$ you may have met as a fact about polyhedra (a cube has $8 - 12 + 6 = 2$). That is no coincidence: the surface of any convex polyhedron, "flattened" onto the plane, is a connected plane graph. The formula is one identity wearing two hats. Note this is Euler's formula for planar graphs — a different result from Euler's theorem in number theory (Chapter 23), which powers RSA. Same prolific mathematician, unrelated theorems.

Edge bounds: the payoff that detects non-planarity

Euler's formula by itself counts faces. Its real power is what it forbids: a planar graph cannot have too many edges. The argument couples Euler's formula with a simple face-counting inequality.

Theorem 33.5 (edge bound for planar graphs). Let $G$ be a connected simple planar graph with $V \ge 3$ vertices and $E$ edges. Then $$E \le 3V - 6.$$ If, in addition, $G$ has no triangles (no 3-cycles), then $E \le 2V - 4$.

The strategy first. Count "edge–face incidences" two ways, a classic double-counting move. Each face is bordered by at least 3 edges (in a simple graph with $\ge 3$ vertices, the smallest possible face boundary is a triangle). Each edge borders at most 2 faces. So $3F \le 2E$. Feed that into Euler's formula $V - E + F = 2$ to eliminate $F$ and the bound on $E$ pops out. For the triangle-free case, the smallest face boundary is a 4-cycle, so the "$3$" becomes a "$4$."

Proof. Fix a plane drawing of $G$ with $F$ faces. Define the degree of a face to be the number of edges on its boundary (an edge counts twice for a face if both of its sides touch that same face, as for a bridge, but in a 2-connected simple graph each face boundary is a simple cycle). Summing face degrees counts each edge exactly twice — once for the face on each side — so $$\sum_{\text{faces } f} \deg(f) = 2E.$$ In a simple graph with $V \ge 3$, every face is bounded by at least 3 edges, so $\deg(f) \ge 3$ for each of the $F$ faces, giving $\sum_f \deg(f) \ge 3F$. Combining, $3F \le 2E$, i.e. $F \le \tfrac{2}{3}E$. Now substitute into Euler's formula: $$2 = V - E + F \le V - E + \tfrac{2}{3}E = V - \tfrac{1}{3}E.$$ Multiplying by 3 and rearranging gives $E \le 3V - 6$. If $G$ is triangle-free, every face boundary has length at least 4, so $4F \le 2E$, i.e. $F \le \tfrac{1}{2}E$; the same substitution yields $2 \le V - \tfrac{1}{2}E$, i.e. $E \le 2V - 4$. $\blacksquare$

Now watch this bound do real work.

$K_5$ is not planar. $K_5$ has $V = 5$ and $E = \binom{5}{2} = 10$. If it were planar, Theorem 33.5 would force $E \le 3V - 6 = 9$. But $10 > 9$. Contradiction — so $K_5$ cannot be drawn without a crossing. $\blacksquare$

$K_{3,3}$ is not planar. $K_{3,3}$ (the complete bipartite graph: three vertices on each side, every cross pair joined) has $V = 6$ and $E = 9$. It is bipartite, hence triangle-free, so the second bound applies: planarity would force $E \le 2V - 4 = 8$. But $9 > 8$. Contradiction. $\blacksquare$

⚠️ Common Pitfall: The edge bound is a one-way test. $E \le 3V - 6$ is necessary for planarity, not sufficient. If a graph violates it, the graph is definitely non-planar (a clean, fast certificate). But many non-planar graphs satisfy $E \le 3V - 6$ and are non-planar for subtler reasons — $K_{3,3}$ satisfies $E = 9 \le 3\cdot 6 - 6 = 12$ and you need the triangle-free bound to catch it. Passing the edge count does not prove planarity; failing it does prove non-planarity.

🔄 Check Your Understanding 1. State Euler's formula and verify it on a 4-cycle drawn in the plane ($V=4$, $E=4$). 2. A connected simple planar graph has 10 vertices. What is the maximum possible number of edges? 3. Use an edge bound to show that $K_6$ is non-planar.

Answers

1. $V - E + F = 2$. A 4-cycle has $V=4, E=4$, and $F=2$ (inside + outside): $4 - 4 + 2 = 2$. ✓
2. $E \le 3V - 6 = 3(10) - 6 = 24$ edges.
3. $K_6$ has $V=6$, $E = \binom{6}{2} = 15$. Planarity would require $E \le 3(6) - 6 = 12$, but $15 > 12$, so $K_6$ is non-planar. (Containing the non-planar $K_5$ also settles it.)

33.4 Kuratowski's theorem: the two forbidden graphs

We now have two "minimal" non-planar graphs, $K_5$ and $K_{3,3}$. The remarkable fact — one of the most elegant characterizations in graph theory — is that these two are the only obstructions to planarity. Every non-planar graph contains one of them, suitably understood, and nothing else can go wrong.

To state it precisely we need one notion. A subdivision of a graph is what you get by replacing some edges with paths — inserting new degree-2 vertices along an edge, like adding beads on a string. Subdividing an edge cannot create or remove a crossing in any essential way (a smoothed-out path crosses other edges exactly when the original edge did), so a graph is planar if and only if every subdivision of it is, and vice versa.

Theorem 33.6 (Kuratowski's theorem). A graph is planar if and only if it contains no subgraph that is a subdivision of $K_5$ or of $K_{3,3}$.

We state this result without proof — its proof is substantial and beyond our scope — but the intuition and the use are very much in scope.

💡 Intuition: Think of $K_5$ and $K_{3,3}$ as the two fundamental "knots" that cannot be undone in the plane. $K_5$ is "five things all mutually connected"; $K_{3,3}$ is "three houses each connected to three utilities" — the classic puzzle of joining three houses to gas, water, and electricity without crossing pipes, which is impossible precisely because $K_{3,3}$ is non-planar. Kuratowski's theorem says these are the whole story: a graph fails to be planar if and only if one of these two knots is hiding inside it (possibly with extra beads strung along its edges). There is no third kind of obstruction.

A closely related statement, Wagner's theorem, replaces "subdivision" with "graph minor" (obtained by deleting and contracting edges) and is often easier to apply: a graph is planar iff it has neither $K_5$ nor $K_{3,3}$ as a minor. For our purposes the two are interchangeable; both say the same two graphs are the only barriers.

Using it. Kuratowski's theorem turns "is this planar?" into a search: hunt for a $K_5$ or $K_{3,3}$ subdivision. If you find one, the graph is non-planar and you have a certificate — a specific structure a skeptic can verify. If you can prove none exists, the graph is planar. The famous Petersen graph, for instance, is non-planar, and the cleanest proof exhibits a $K_{3,3}$ subdivision inside it. Note the asymmetry with the edge bound of section 33.3: the edge bound is a fast necessary test (easy to fail, can't confirm planarity), whereas Kuratowski gives an exact characterization (but finding the forbidden subdivision can take work).

🔄 Check Your Understanding 1. The "three houses, three utilities" puzzle asks you to connect 3 houses to 3 utilities with no crossing pipes. Which graph is this, and is it solvable? 2. What does it mean to "subdivide" an edge, and why doesn't subdivision change whether a graph is planar? 3. Kuratowski says non-planarity has exactly two root causes. Name them.

Answers

1. It is $K_{3,3}$. It is not solvable in the plane, because $K_{3,3}$ is non-planar (we proved $E = 9 > 8 = 2V-4$).
2. Subdividing an edge replaces it with a path by inserting new degree-2 vertices along it. It can't change planarity because a path can be drawn following the exact route of the original edge, so crossings are neither created nor removed.
3. Containing a subdivision (or minor) of $K_5$, or of $K_{3,3}$. Those are the only two obstructions.

33.5 The Four Color Theorem

We can finally state the theorem the chapter is named for, the one that connects coloring (section 33.1) to planarity (sections 33.3–33.4).

Theorem 33.7 (The Four Color Theorem). Every planar graph is 4-colorable. Equivalently, the regions of any map drawn in the plane can be colored with four colors so that regions sharing a border get different colors.

The map and graph versions are the same statement: as in section 33.2, a map becomes a planar graph (one vertex per region, edges between bordering regions), and a proper 4-coloring of that graph is a 4-coloring of the map. So "four colors suffice for any map" and "$\chi(G) \le 4$ for every planar graph $G$" say the same thing.

Why four, and why it was so hard

That you need at least four colors is easy: draw four mutually-bordering countries (e.g. one central region touching three others that also touch each other), realize $K_4$ as a map, and you have a planar graph with $\chi = 4$. So three colors are not always enough.

That four colors are always enough is one of the hardest-won theorems in mathematics. The conjecture was raised in 1852 by Francis Guthrie, a student coloring a map of England's counties. For over a century it resisted proof, attracting flawed "proofs" from serious mathematicians — most famously Alfred Kempe's 1879 argument, accepted for eleven years before Percy Heawood found a fatal gap in 1890. Heawood salvaged enough of Kempe's idea to prove the five-color theorem (every planar graph is 5-colorable), which is fully provable by hand and which you will prove in the exercises. But the gap between five and four stayed open for another 86 years.

🚪 Threshold Concept: when a proof is too big for a human. In 1976 Kenneth Appel and Wolfgang Haken proved the Four Color Theorem — by reducing it to a finite but enormous case analysis and then checking the cases by computer. They identified an "unavoidable set" of 1,936 reducible configurations (later refined to fewer) and used a program to verify that each could be handled. No human has ever checked every case by hand; the proof's validity rests, in part, on trusting that the program (and the hardware it ran on) was correct.

This shattered an assumption mathematicians had never had to question: that a proof is something a person can, in principle, read and verify. The Four Color Theorem was the first major result where that was not literally true. It provoked a genuine philosophical crisis — is a theorem proven if no human can survey the proof? — that has only deepened in the era of formal proof assistants and machine-checked mathematics. (In 2005 Georges Gonthier and Benjamin Werner produced a proof formally verified by the Coq proof assistant, which moved the trust from "a one-off program" to "a small, scrutinized proof-checking kernel" — but did not eliminate the computer from the loop.)

For a programmer this lands differently than for a classical mathematician. Of course we trust computations we cannot hand-check — we do it every time we ship. The Four Color Theorem is where mathematics had to confront the question software engineers live with daily: how do you trust a result produced by a machine? Theme two of this book — proofs guarantee correctness in a way tests do not — meets its hardest case study here. A computer-assisted proof still settles all cases (unlike a test suite), but only if you trust the machinery that checked them.

⚠️ Common Pitfall: what the Four Color Theorem does not say. It does not say every graph is 4-colorable — that is wildly false ($K_5$ needs five colors, $K_{100}$ needs a hundred). It applies only to planar graphs. It also does not say four colors are always necessary (many maps do fine with two or three); it says four always suffice. And it requires regions to be connected — a country split into two disconnected pieces (an exclave) that both must share a color can break the four-color bound, which is why the theorem is stated for ordinary plane graphs where each region is one connected blob.

🔗 Connection. The contrast with section 33.1 is the whole point. For general graphs, $\chi$ can be as large as the number of vertices and is NP-hard to compute. For planar graphs, the structure imposed by "drawable without crossings" — the same structure that gave us Euler's formula and the edge bound — forces $\chi \le 4$, always. Planarity is a powerful constraint: it is exactly the kind of structural restriction that turns a hard problem into a bounded one. (Deciding whether a planar graph is 3-colorable, however, remains NP-complete — the jump from 4 to 3 is where the difficulty hides.)

🔄 Check Your Understanding 1. Does the Four Color Theorem imply $K_5$ is 4-colorable? Explain. 2. What is the five-color theorem, and why is it historically important here? 3. In one sentence, what made the Appel–Haken proof philosophically controversial?

Answers

1. No. $K_5$ is not planar (we proved $E = 10 > 9 = 3V-6$), so the theorem doesn't apply to it; in fact $\chi(K_5) = 5$. The theorem is about planar graphs only.
2. The five-color theorem says every planar graph is 5-colorable; it is provable by hand (Heawood, 1890) and was the best known result for 86 years before the four-color result was proved by computer.
3. It was the first major theorem whose proof required checking a huge number of cases by computer, so no human could verify it entirely by hand — raising the question of whether a proof no person can survey is really a proof.

33.6 Greedy coloring and its limits

The clique/degree bounds told us $\chi(G) \le \Delta(G) + 1$, and the proof was an algorithm: color vertices one at a time, each getting the smallest color its neighbors haven't used. That algorithm is greedy coloring, and it is what real systems actually run, because computing $\chi$ exactly is intractable. The catch — and the lesson — is that greedy's result depends heavily on the order in which you process the vertices.

Definition (greedy coloring). Given a graph $G$ and an ordering $v_1, v_2, \dots, v_n$ of its vertices, greedy coloring assigns to each $v_i$, in order, the smallest positive integer color not already assigned to any neighbor of $v_i$ that precedes it in the order.

Greedy is fast (linear in the size of the graph) and always produces a proper coloring. What it does not guarantee is the minimum number of colors. Two facts bound its behavior:

• Upper bound. Greedy never uses more than $\Delta(G) + 1$ colors, for any order — that was Theorem 33.2.
• Order dependence. For some graphs the worst order makes greedy use far more colors than $\chi(G)$, even on a graph that is 2-colorable.

The second point is the cautionary tale. Here is the classic construction.

The strategy first (constructing greedy's worst case). We want a graph that is genuinely 2-colorable ($\chi = 2$) but on which a bad vertex order forces greedy to use as many colors as we like. Take a crown graph: two groups of $n$ vertices, $a_1,\dots,a_n$ and $b_1,\dots,b_n$, with an edge $a_i b_j$ whenever $i \ne j$ (each $a$ joined to every $b$ except its "partner"). This is bipartite, so $\chi = 2$. But order the vertices $a_1, b_1, a_2, b_2, \dots, a_n, b_n$ and watch greedy get fooled into giving each pair a brand-new color.

Example. Take the crown graph with $n = 3$: vertices $a_1,a_2,a_3,b_1,b_2,b_3$; edges $a_i b_j$ for $i \ne j$. It is bipartite (all edges go between the $a$'s and the $b$'s), so $\chi = 2$ — color every $a$ with 1 and every $b$ with 2 and done.

Now run greedy in the order $a_1, b_1, a_2, b_2, a_3, b_3$:

• $a_1$: no colored neighbors yet → color 1.
• $b_1$: its neighbors are $a_2, a_3$ (not $a_1$, since $i \ne j$); neither is colored yet → smallest free color 1.
• $a_2$: neighbors $b_1, b_3$; $b_1$ has color 1 → smallest free color 2.
• $b_2$: neighbors $a_1, a_3$; $a_1$ has color 1 → smallest free color 2.
• $a_3$: neighbors $b_1, b_2$; colors 1 and 2 used → smallest free color 3.
• $b_3$: neighbors $a_1, a_2$; colors 1 and 2 used → smallest free color 3.

Greedy used three colors on a graph whose chromatic number is two. With $n$ pairs and this adversarial order, greedy uses $n$ colors against an optimum of 2 — arbitrarily bad. Yet a good order (all $a$'s first, then all $b$'s) makes greedy find the optimal 2-coloring immediately.

⚠️ Common Pitfall: Greedy coloring is correct (always proper) but not optimal, and the gap can be enormous. Never report greedy's color count as "the chromatic number." It is an upper bound on $\chi(G)$, nothing more. The order matters enormously, which is why real allocators invest in good vertex orderings.

Choosing a better order

Since order is everything, good heuristics order vertices cleverly. The best-known is Welsh–Powell: sort vertices by decreasing degree and color in that order, on the logic that high-degree (highly-constrained) vertices should be handled while colors are still plentiful. Another is smallest-last ordering, which repeatedly removes a minimum-degree vertex and colors in the reverse of the removal order; for planar graphs this provably uses at most 6 colors (the basis of the six-color theorem in the exercises). None of these heuristics is guaranteed optimal — they cannot be, since optimal coloring is NP-hard — but they are vastly better than an adversarial order and are what production register allocators and schedulers use.

🔗 Connection. This is theme four again — computation and proof are complementary — with a twist. We cannot compute $\chi$ exactly at scale (Chapter 37 explains why: it is NP-hard). So we prove bounds ($\omega \le \chi \le \Delta+1$, planar $\le 4$) that frame the answer, and we compute a good-enough coloring with a fast heuristic. The proof tells you the target; the heuristic gets you a usable answer; together they ship a working compiler. Knowing greedy's worst case is what stops you from trusting it blindly.

🐛 Find the Error. A student claims: "Greedy coloring with vertices sorted by decreasing degree always produces an optimal coloring, because it handles the hardest vertices first." Is this correct? If not, what is the precise claim that is true?

Answer

It is false. No polynomial-time algorithm — greedy with any fixed ordering rule included — is known to always produce an optimal coloring, because graph coloring is NP-hard (Chapter 37); if Welsh–Powell were always optimal it would solve an NP-hard problem in polynomial time. The true claim is weaker: decreasing-degree ordering (Welsh–Powell) is a good heuristic that often does well and never exceeds $\Delta(G)+1$ colors, but it can still be beaten on adversarial inputs and is not guaranteed optimal. "Handles the hardest vertices first" is good intuition for why it tends to help, not a proof of optimality.

Project Checkpoint: coloring in the Toolkit

We have been building the graphs.py module of dmtoolkit since Chapter 27 — a Graph class plus traversals (bfs, dfs) and path/tree algorithms. This chapter adds the coloring operations: a fast greedy colorer and a brute-force exact chromatic number for small graphs, so you can both ship a coloring and check how far off greedy is on cases small enough to verify.

Add to dmtoolkit/graphs.py (we assume Graph exposes vertices() and neighbors(v) from Chapter 27):

def greedy_coloring(g, order=None):
    """Proper coloring via the greedy rule. Returns {vertex: color (int >= 0)}.
    Color count = 1 + max(color.values()). NOT guaranteed minimal (see Ch. 33)."""
    order = list(g.vertices()) if order is None else order
    color = {}
    for v in order:
        used = {color[u] for u in g.neighbors(v) if u in color}
        c = 0
        while c in used:          # smallest color not used by a colored neighbor
            c += 1
        color[v] = c
    return color

def chromatic_number(g):
    """EXACT chi(G) by brute force. Exponential time -- small graphs only."""
    from itertools import product
    verts = list(g.vertices())
    for k in range(1, len(verts) + 1):              # try k = 1, 2, 3, ...
        for assign in product(range(k), repeat=len(verts)):
            c = dict(zip(verts, assign))
            if all(c[u] != c[v] for u in verts for v in g.neighbors(u)):
                return k                            # first k that works is chi(G)
    return len(verts)

Trace greedy_coloring on the 5-cycle $C_5$ with vertices [0,1,2,3,4] and edges 0-1-2-3-4-0, in natural order: vertex 0 → color 0; vertex 1 (neighbor 0 has color 0) → 1; vertex 2 (neighbor 1 has 1) → 0; vertex 3 (neighbor 2 has 0) → 1; vertex 4 (neighbors 0 and 3 have colors 0 and 1) → 2. Greedy uses 3 colors, which equals $\chi(C_5)=3$ here — the bound is tight for odd cycles. chromatic_number on the same graph returns 3, confirming greedy was optimal this time. Run both on the crown graph from 33.6 and you will see greedy's count exceed chromatic_number's — your Toolkit now measures the gap that section 33.6 warned about.

Toolkit so far: graphs.py now carries the full graph engine — representation, BFS/DFS (Ch. 28), shortest paths and MST (Ch. 29, 32), and now coloring. This is the exact machinery the capstone's social-network analyzer (Chapter 39, Track B) calls on to partition a friendship graph into conflict-free groups.

Summary

Coloring.

Standard chromatic numbers: $\chi(K_n) = n$; $\chi(C_n) = 2$ (even $n$), $3$ (odd $n$); trees and bipartite graphs (with an edge) $= 2$.

Planarity.

The Four Color Theorem. Every planar graph is 4-colorable ($\chi \le 4$). At least 4 are sometimes needed ($K_4$ as a map). Proved by Appel–Haken (1976) via computer-checked case analysis — the first major theorem of that kind; formally verified in Coq by Gonthier–Werner (2005). Does not apply to non-planar graphs.

Greedy coloring. Process vertices in some order; give each the smallest color no earlier neighbor uses. Always proper; uses $\le \Delta(G)+1$ colors; not optimal — a bad order on a 2-colorable crown graph forces arbitrarily many colors. Heuristic orders (Welsh–Powell = decreasing degree; smallest-last) help but cannot guarantee optimality (coloring is NP-hard).

Decision aid.

Spaced Review

Answer from memory before checking. These revisit Chapters 30 and 27.

1. (Ch. 30) The Four Color Theorem's proof reduced an infinite problem to a large finite case analysis. Chapter 30 drew an "easy vs. hard" boundary between two superficially similar problems. Which two, and which side of that boundary is coloring (deciding 3-colorability) on?
2. (Ch. 30) Euler paths (Ch. 30) and Euler's formula (this chapter) are both named for Euler but are different results. State each in one sentence.
3. (Ch. 27) Define the chromatic number using only terms from Chapter 27 (vertex, edge, adjacent).
4. (Ch. 27) The handshaking lemma (Ch. 27) says $\sum_v \deg(v) = 2E$. We used a face-degree analogue ($\sum_f \deg(f) = 2E$) to prove the planar edge bound. What is the one shared counting principle behind both?

Answers

1. Euler paths/circuits (easy, polynomial) vs. Hamilton paths/circuits and the TSP (hard, NP-hard preview). Deciding 3-colorability is on the hard side — it is NP-complete (formalized in Ch. 37), like Hamilton/TSP, not like the easy Euler-path test.
2. Euler path: a walk using every edge exactly once, which exists in a connected graph iff zero or two vertices have odd degree. Euler's formula: for a connected plane graph, $V - E + F = 2$.
3. The chromatic number is the smallest number of colors needed to label every vertex so that no two adjacent vertices (vertices joined by an edge) share a label.
4. Double counting: count edge-endpoint (or edge-side) incidences two ways. Each edge has two endpoints (handshaking) and, in a plane graph, two sides/faces (face-degree sum); summing the local counts gives $2E$ both times.

What's Next

Coloring partitioned a graph to separate conflicting vertices. The next chapter asks the opposite kind of question about graphs with capacities: how much stuff can you push through a network from a source to a sink, and how do you pair things up optimally? Network flow and matching (Chapter 34) develops the max-flow problem, the Ford–Fulkerson method, the elegant max-flow min-cut duality, and bipartite matching — the tool that optimally assigns workers to jobs, applicants to schools, and, fittingly, brings the bipartite graphs we met here back for one more starring role. It is the capstone of Part V's algorithmic toolkit and the last graph algorithm before we turn, in Part VI, to the ultimate questions of what computers can and cannot do.