Combinatorics and discrete mathematics

Graph coloring and the four color theorem

Assigning colors to vertices or regions so neighbors differ; every planar map needs at most four colors.

IntuitionVisual intuition: coloring maps

Imagine coloring the countries on a political map so that any two countries sharing a border always get different colors. This is exactly the graph coloring problem: turn each region into a vertex, and draw an edge between two vertices whenever the two regions are neighbors. A proper coloring assigns a color to every vertex so that the two endpoints of every edge always receive different colors. The smallest number of colors that makes this possible is called the chromatic number, written $\chi(G)$ .

A planar map graph with a valid 4-coloring: no two adjacent regions share a color.

SchoolProper coloring and the chromatic number

Definition: Proper coloring, chromatic number

A proper $k$ -coloring of a graph $G$ is a function that assigns one of $k$ colors to every vertex so that no two adjacent vertices get the same color. The chromatic number $\chi(G)$ is the smallest $k$ for which a proper $k$ -coloring exists. Equivalently, $\chi(G)$ is the smallest number of independent sets (sets of pairwise non-adjacent vertices) needed to partition all of $V(G)$ .

\chi(G) = \min\{k \in \mathbb{N} : G \text{ is properly } k\text{-colorable}\}

Here $k$ ranges over the natural numbers, $G$ is the graph being colored, and $\chi(G)$ is the resulting minimum. A useful, easy upper bound comes from the greedy algorithm: order the vertices arbitrarily and color each vertex with the first color not already used by an earlier neighbor. Since every vertex has at most $\Delta(G)$ neighbors, this never needs more than $\Delta(G)$ + 1 colors, giving $\chi(G) \le \Delta(G) + 1$ .

\chi(G) \le \Delta(G) + 1

Chromatic number and chromatic polynomial for common graph families
Graph family	Chromatic number	Chromatic polynomial
Complete graph $K_n$	$n$	$P(K_n,k) = k(k-1)(k-2)\cdots(k-n+1)$
Tree $T$ on $n$ vertices	$2$ (if $n \ge 2$ )	$P(T,k) = k(k-1)^{n-1}$
Cycle $C_n$ , $n$ odd	$3$	$P(C_n,k) = (k-1)^n + (-1)^n(k-1)$
Every planar graph	at most $4$ (Four Color Theorem)	no closed form in general

UndergraduateThe chromatic polynomial

Beyond just the chromatic number, we can count the number of proper $k$ -colorings of $G$ exactly: this count is a polynomial in $k$ , called the chromatic polynomial $P(G,k)$ . It satisfies the deletion-contraction recurrence: pick any edge $e$ of $G$ , delete it to get $G-e$ , or contract it (merge its two endpoints into one) to get $G/e$ ; then $P(G,k) = P(G-e,k) - P(G/e,k)$ . For the complete graph $K_n$ , every vertex must get a different color, so $P(K_n,k) = k(k-1)(k-2)\cdots(k-n+1)$ . For a tree $T$ with $n$ vertices, the recurrence gives $P(T,k) = k(k-1)^{n-1}$ , since the first vertex can take any of $k$ colors and each subsequent vertex (attached by one edge) can take any color but its parent's.

P(G,k) = P(G-e,k) - P(G/e,k)

P(K_n,k) = k(k-1)(k-2)\cdots(k-n+1)

UndergraduateKey theorems

Theorem: The Five Color Theorem

Every planar graph $G$ satisfies $\chi(G) \le 5$ .

Why is it true?

This is a much easier warm-up to the Four Color Theorem: it uses only elementary induction and a clever local swapping trick (a Kempe chain), with no computer assistance, so a reader can verify every step by hand.

Proof

Base case. If $G$ has at most 5 vertices, color each vertex a different color; at most 5 colors are used, so the claim holds.

Inductive step, setup. Assume every planar graph with fewer than $n$ vertices is 5-colorable, and let $G$ be planar with $n$ vertices. Every simple planar graph satisfies $E \le 3V - 6$ (edge bound proved via Euler's formula), so the sum of all degrees is at most $2(3n-6) = 6n-12$ , which is less than $6n$ . Hence the average degree is less than 6, so some vertex $v$ has degree at most 5.

Remove $v$ to get a smaller planar graph with $n-1$ vertices; by the inductive hypothesis it has a proper 5-coloring. If $v$ has at most 4 neighbors, at most 4 colors are used among them, leaving a free color for $v$ , and we are done.

The remaining case is deg $(v) = 5$ and all 5 colors appear, once each, among the 5 neighbors of $v$ . List the neighbors in the cyclic order they appear around $v$ in the planar drawing as first, second, third, fourth, fifth, colored 1, 2, 3, 4, 5 respectively. Consider the subgraph $H_{1,3}$ formed by all vertices colored 1 or 3. If the first and third neighbors lie in different connected components of $H_{1,3}$ , swap colors 1 and 3 throughout the component containing the first neighbor; this stays a proper coloring (it only touches vertices colored 1 or 3), and now the first neighbor is colored 3, so color 1 is free for $v$ .

Otherwise the first and third neighbors lie in the same component of $H_{1,3}$ , joined by a path alternating colors 1 and 3. Together with $v$ and the two edges to the first and third neighbors, this path closes a cycle in the plane that separates the second neighbor from the fourth neighbor (by the Jordan curve theorem, since the cyclic order around $v$ is first, second, third, fourth, fifth). Consequently no path of alternating colors 2 and 4 can connect the second and fourth neighbors, since such a path would have to cross the 1-3 cycle. So we swap colors 2 and 4 throughout the component of $H_{2,4}$ containing the second neighbor; this frees color 2 for $v$ .

In every case $v$ receives one of the 5 colors without conflicting with any neighbor, extending the coloring of $G$ -v to all of $G$ . By induction, $\chi(G) \le 5$ for every planar graph.

Theorem: The Four Color Theorem

Every planar graph $G$ satisfies $\chi(G) \le 4$ .

Why is it true?

This settles the original map-coloring question asked by Francis Guthrie in 1852: four colors always suffice for any planar map, and this bound is tight, since some planar graphs (for example a map with four mutually bordering regions) genuinely require all four colors.

Proof

Reduction to a minimal counterexample. If the theorem were false, take a planar graph requiring 5 or more colors with the fewest possible vertices. Adding edges to a planar graph while keeping it planar can only increase the number of colors needed, so this minimal counterexample can be assumed to be a maximal planar graph (a triangulation), where every face, including the outer one, is bounded by exactly 3 edges.

Discharging setup. Assign to every vertex $v$ an initial charge $6 - \deg(v)$ . Using $V - E + F = 2$ together with $2E = \sum_v \deg(v)$ and $3F \le 2E$ (each face has at least 3 sides), the total charge over all vertices works out to exactly $12$ , hence strictly positive. The discharging method then moves charge locally between nearby vertices according to a fixed set of rules, without changing this total; analyzing where positive charge must remain after redistribution shows that some vertex of low degree, together with a specific pattern of neighbors, must occur somewhere in the graph. These finitely many patterns are called the unavoidable configurations, since at least one of them is present in every planar triangulation.

Reducibility. A configuration is called reducible if, whenever it appears inside a hypothetical minimal counterexample, any 4-coloring of the smaller graph obtained by removing or contracting that configuration can always be re-extended to a 4-coloring of the whole graph, contradicting minimality. Appel and Haken (1976) verified computationally that every configuration in their unavoidable list of 1,936 configurations (later trimmed to 633 by Robertson, Sanders, Seymour and Thomas in 1997) is reducible, using well over a thousand hours of computer time. This made the Four Color Theorem the first major theorem whose proof relied essentially on machine computation, later independently re-verified and, in 2005, formally checked line by line inside the Coq proof assistant by Gonthier.

Conclusion. Since every unavoidable configuration is reducible, no minimal counterexample can exist: no planar graph needs 5 or more colors, so $\chi(G) \le 4$ for every planar graph $G$ .

UndergraduateReal-World Applications and Worked Examples

Graph coloring shows up whenever different tasks must be kept apart because they conflict, but tasks that do not conflict can share a resource. Compilers use it to assign a limited number of CPU registers to program variables (register allocation): two variables that are both "alive" at the same time get an edge, and a valid register assignment is exactly a proper coloring. Universities use it to schedule final exams: two courses sharing a student get an edge, and the minimum number of exam time slots is the chromatic number of that conflict graph. Wireless networks use it to assign radio frequencies to transmitters so that nearby transmitters (which would interfere) never share a frequency.

Example: Register allocation for four temporary variables

A compiler tracks four temporary variables $a, b, c, d$ in a loop. Their live ranges overlap as follows: $a$ overlaps with $b$ and $c$ ; $b$ overlaps with $a$ , $c$ and $d$ ; $c$ overlaps with $a$ , $b$ and $d$ ; $d$ overlaps with $b$ and $c$ only. Build the conflict graph and find the minimum number of CPU registers needed.

Solution

Build the graph. Vertices $a, b, c, d$ ; edges $ab, ac, bc, bd, cd$ (from the overlaps listed), and no edge $ad$ since $a$ and $d$ never overlap.

Look for a triangle. Vertices $a, b, c$ are pairwise adjacent ( $ab$ , $ac$ , $bc$ all present), so this graph contains a triangle, meaning at least 3 registers are needed: 2 registers can never properly color a triangle, since any 2-coloring forces two of the three mutually adjacent vertices to share a color.

Try 3 colors (registers) $1, 2, 3$ . Set $a=1$ , $b=2$ , $c=3$ (forced distinct since they form a triangle). Now check $d$ : $d$ is adjacent to $b$ (color 2) and $c$ (color 3) but not to $a$ , so $d$ can safely take color 1.

Conclusion. The coloring $a=1, b=2, c=3, d=1$ is proper, so 3 registers suffice, and 3 is also necessary because of the triangle $\{a,b,c\}$ . The minimum number of registers is 3.

Example: Exam scheduling with the fewest time slots

A university offers five courses $1, 2, 3, 4, 5$ . Some pairs share at least one enrolled student and so cannot be examined at the same time: pairs $(1,2)$ , $(1,3)$ , $(2,3)$ , $(2,4)$ , $(3,4)$ , $(4,5)$ conflict; all other pairs have no student in common. Find the minimum number of exam time slots needed so that no student has two exams at once.

Solution

Model as a graph. Vertices $1,2,3,4,5$ are the courses; draw an edge for every conflicting pair: $12, 13, 23, 24, 34, 45$ . The minimum number of exam slots is exactly $\chi(G)$ of this conflict graph, since two courses can share a slot precisely when they are non-adjacent.

Find a lower bound. Vertices $1, 2, 3$ are pairwise adjacent ( $12, 13, 23$ all present), so they form a triangle; as in any triangle, 2 colors are not enough, so at least 3 slots are required.

Try 3 slots. Assign course $1$ to slot A, course $2$ to slot B, course $3$ to slot C (forced distinct by the triangle). Course $4$ conflicts with $2$ (slot B) and $3$ (slot C) but not with $1$ , so course $4$ can go in slot A. Course $5$ conflicts only with $4$ (slot A), so course $5$ can go in slot B (or C).

Conclusion. Slot A $= \{1, 4\}$ , slot B $= \{2, 5\}$ , slot C $= \{3\}$ is a valid schedule with no conflicts, and 3 is optimal because of the triangle $\{1,2,3\}$ . So 3 exam slots are needed and sufficient.

Research frontier as of 2026

The Four Color Theorem is fully settled, but research around it is still active. One direction seeks a shorter, more human-checkable proof: Robertson, Sanders, Seymour and Thomas simplified the configuration count from Appel and Haken's 1,936 down to 633 in 1997, and Gonthier's 2005 machine-checked proof in the Coq proof assistant removed any residual doubt about hidden computer bugs, but no proof avoiding case-by-case computer search is known, and many mathematicians consider finding one a major open problem. Another active direction is the Heawood conjecture on coloring maps on surfaces of higher genus (such as a torus), which was fully proved in 1968 by Ringel and Youngs except for the sphere case (settled separately by the Four Color Theorem itself); current work extends discharging and reducibility techniques from planar graphs to structured families such as graphs embeddable on other surfaces and to list-coloring variants, where the list-chromatic number can exceed $\chi(G)$ even though it equals 4 for all planar graphs by a 1994 theorem of Thomassen.

What is the chromatic number $\chi(G)$ of the complete graph $K_5$ on 5 vertices?

A graph $G$ has maximum degree $\Delta(G)$ $= 4$ . What is the best upper bound on $\chi(G)$ guaranteed by the greedy coloring bound?

In what year did Appel and Haken publish the first proof of the Four Color Theorem, relying on a computer to check thousands of unavoidable configurations?

A university models exam conflicts as a graph $G$ : each course is a vertex, and two courses are joined by an edge whenever some student is enrolled in both. What does the minimum possible number of exam time slots equal?

References

Kenneth Appel, Wolfgang Haken (1977). Every Planar Map Is Four Colorable, Part I: Discharging
Neil Robertson, Daniel P. Sanders, Paul Seymour, Robin Thomas (1997). The Four-Colour Theorem
Georges Gonthier (2008). Formal Proof—The Four-Color Theorem
Reinhard Diestel (2017). Graph Theory