Planar Graphs
Throughout Introduction to Graph Theory and
the pages that followed, we treated graphs as purely combinatorial objects — sets of vertices
and edges, with no reference to geometry or space. We asked questions about
paths,
Eulerian and Hamiltonian cycles,
trees, and
flows — all of which depend only on the
abstract structure \(G = (V, E)\). We now ask a fundamentally different kind of question:
can a graph be drawn in the plane without edges crossing?
This is the first point in Section IV where geometry enters the picture. The answer depends not only
on the combinatorics of \(G\) but on the topology of the surface on which we attempt to embed it.
This shift — from the purely combinatorial to the topological — opens a path that will eventually
lead us to simplicial complexes and homology.
Planar and Plane Graphs
Definition: Plane Graph
A plane graph is a graph \(G = (V, E)\) together with a specific drawing in
the plane \(\mathbb{R}^2\) in which:
- Each vertex \(v \in V\) is mapped to a distinct point in \(\mathbb{R}^2\).
- Each edge \(\{u, v\} \in E\) is drawn as a Jordan arc (a homeomorphic
image of the closed interval \([0, 1]\)) whose two endpoints are the points
representing \(u\) and \(v\).
- The interior of each edge arc contains no vertex.
- No two edges share a point except at a common endpoint.
A graph \(G\) is called planar if it admits at least one such drawing. The
drawing itself is called a planar embedding (or plane embedding)
of \(G\).
The distinction matters: a planar graph is an abstract graph with a certain property,
while a plane graph is a concrete drawing. The same planar graph can have many different
plane embeddings. For our purposes, the key is that a planar embedding carves the plane into
well-defined regions.
Faces
Definition: Face
Given a plane graph \(G\), let \(|G| \subset \mathbb{R}^2\) denote the union of all
vertex points and edge arcs. The faces of the embedding are the
connected components of \(\mathbb{R}^2 \setminus |G|\). Since \(|G|\) is compact
(a finite union of points and Jordan arcs), the complement \(\mathbb{R}^2 \setminus |G|\)
has exactly one unbounded component, called the outer face (or
infinite face); the remaining components are the bounded faces.
Consider the complete graph \(K_4\). In its standard planar embedding (a triangle with one
vertex inside), there are exactly four faces: three bounded triangular regions and one unbounded
outer face (itself bounded by three edges). We write \(F = 4\), and together with \(V = 4\)
vertices and \(E = 6\) edges, we have \(V - E + F = 4 - 6 + 4 = 2\). This is not a coincidence.
Every face is bounded by a closed walk of edges called its boundary. In a simple,
2-connected plane graph — that is, a graph with at least 3 vertices that
remains connected after the deletion of any single vertex — each face boundary is a cycle.
In general, a face boundary may traverse an edge twice (once from each side) if removing
that edge would disconnect the graph.
Faces as Proto-Simplices
The notion of a face is our first encounter with a concept that transcends dimension 1 in
graph theory. A graph has vertices (0-dimensional) and edges (1-dimensional). A plane embedding
adds faces (2-dimensional regions). This triple \((V, E, F)\) — counting objects
by dimension — foreshadows the f-vector \((f_0, f_1, f_2, \ldots)\) of
a simplicial complex, where \(f_k\) counts the \(k\)-dimensional simplices. Planar graphs
are, in a precise sense, the 2-dimensional beginning of a story that extends to arbitrary dimension.
Euler's Formula
The arithmetic identity \(V - E + F = 2\) we observed for \(K_4\) is no accident.
It holds for every connected plane graph and is one of the most beautiful results in
all of mathematics, connecting combinatorics, geometry, and — as we shall see — topology.
Proof:
Choose any
spanning tree \(T\)
of \(G\). Since \(T\) is a tree on \(V\) vertices, it has \(V - 1\) edges
(as established in Trees & Enumeration).
As a plane graph, \(T\) has no cycles and therefore exactly one face (the entire complement
is connected), so \(V - (V-1) + 1 = 2\). The formula holds for \(T\).
Now consider any edge \(e \in E(G) \setminus E(T)\). Since \(T\) is a spanning tree
and \(e \notin E(T)\), the edge \(e\) lies in the interior of some face and connects
two vertices already connected by a path in \(T\). Adding \(e\) back into the plane graph
splits that face into two — the cycle formed by \(e\) together with the unique \(T\)-path
between its endpoints separates the face. Thus adding \(e\) increases both \(E\) and \(F\)
by exactly 1, leaving \(V - E + F\) unchanged. Adding the remaining
\(E - (V - 1)\) edges one by one, each preserving the alternating sum, gives
\(V - E + F = 2\) for the full graph \(G\).
Topological note. Two intuitively obvious facts underlie this proof,
both consequences of the Jordan Curve Theorem (a simple closed curve
in \(\mathbb{R}^2\) separates the plane into exactly two connected components, an
interior and an exterior): (i) the complement of an embedded acyclic graph (such as a
spanning tree) is a single connected region, justifying \(F = 1\) for \(T\); and
(ii) the simple closed curve formed by a non-tree edge \(e\) and the unique \(T\)-path
between its endpoints splits its enclosing face into exactly two sub-regions,
justifying \(\Delta F = 1\) at each step. We invoke these classical topological
results without proof.
Consequences for Edge Density
Euler's formula constrains how many edges a planar graph can have. The key observation
is that every face boundary walk has length at least 3 (in a simple graph with \(V \geq 3\)),
while the total length summed over all faces equals \(2E\) — each edge contributing
exactly twice.
Corollary: Edge Bound for Planar Graphs
Let \(G\) be a simple connected planar graph with \(V \geq 3\) vertices and \(E\) edges. Then
\[
E \leq 3V - 6.
\]
Proof:
Sum the boundary walk lengths over all faces. Each edge contributes exactly 2 to this
sum: a non-bridge edge appears once in each of the two distinct face boundaries it
separates, while a bridge edge appears twice in the boundary walk of the single face
it lies in (once from each side). The total is therefore \(2E\).
On the other hand, in a simple graph with \(V \geq 3\) and \(E \geq 1\), each face
boundary walk has length at least 3: lengths 1 and 2 would require a loop or a pair
of parallel edges, both excluded by simplicity. Summing over the \(F\) faces gives
a lower bound of \(3F\). Hence \(2E \geq 3F\), so \(F \leq \frac{2}{3}E\).
Substituting into Euler's formula:
\(2 = V - E + F \leq V - E + \frac{2}{3}E = V - \frac{1}{3}E\),
giving \(E \leq 3V - 6\).
Corollary: Edge Bound for Triangle-Free Planar Graphs
If \(G\) is a simple connected triangle-free planar graph with \(V \geq 3\), then
\[
E \leq 2V - 4.
\]
Proof:
The boundary walk sum identity \(2E = \sum_f (\text{length of } \partial f)\) from the
previous proof still holds. Since \(G\) is simple and triangle-free with \(V \geq 3\), each face
boundary walk has length at least 4: a closed walk of length 3 in a simple graph is
a triangle, which is excluded by hypothesis; lengths 1 and 2 are excluded by simplicity.
Summing gives \(2E \geq 4F\), so \(F \leq \frac{1}{2}E\). Euler then yields
\(2 \leq V - E + \frac{1}{2}E = V - \frac{1}{2}E\), hence \(E \leq 2V - 4\).
Non-Planarity of \(K_5\) and \(K_{3,3}\)
These corollaries immediately settle two fundamental non-planarity results.
Proposition: \(K_5\) is Non-Planar
The complete graph \(K_5\) has \(V = 5\) and
\(E = \binom{5}{2} = 10\). The edge bound gives \(E \leq 3(5) - 6 = 9\).
Since \(10 > 9\), \(K_5\) is not planar.
Proposition: \(K_{3,3}\) is Non-Planar
The complete bipartite graph \(K_{3,3}\) has \(V = 6\) and \(E = 9\). Since
\(K_{3,3}\) is bipartite, it contains no
odd cycles and in particular is triangle-free. The triangle-free bound gives
\(E \leq 2(6) - 4 = 8\). Since \(9 > 8\), \(K_{3,3}\) is not planar.
Minimum Degree Bound
A further consequence of the edge bound is a structural constraint on vertex degrees.
Corollary: Every Planar Graph Has a Vertex of Degree \(\leq 5\)
Let \(G\) be a simple planar graph. Then \(G\) contains a vertex \(v\) with
\(\deg(v) \leq 5\).
Proof:
It suffices to prove the claim for each connected component of \(G\). A component
with \(V \leq 2\) trivially has a vertex of degree \(\leq 1\). For a connected
component with \(V \geq 3\), suppose for contradiction that every vertex has
degree \(\geq 6\). By the
Handshaking Lemma,
\(2E = \sum_{v} \deg(v)\); since \(\deg(v) \geq 6\) for all \(v\), we have
\(\sum_{v} \deg(v) \geq 6V\), so \(E \geq 3V\). But \(E \leq 3V - 6 < 3V\)
for any connected planar graph with \(V \geq 3\), a contradiction.
This innocent-looking corollary is the engine behind the graph coloring results in the
final section of this page.
Euler Characteristic as a Topological Invariant
The quantity \(\chi = V - E + F\) is called the Euler characteristic.
For any connected plane graph, \(\chi = 2\). Remarkably, this value depends only on the
topology of the surface — the sphere \(S^2\) (which is topologically equivalent to the
plane plus a point at infinity) has \(\chi = 2\) regardless of how we triangulate or
embed a graph on it. This is a shadow of a much deeper fact: Euler characteristic is a
topological invariant, unchanged by continuous deformations
(homeomorphisms).
The alternating sum \(\chi = f_0 - f_1 + f_2\) generalizes to simplicial complexes
of arbitrary dimension as \(\chi(K) = \sum_{k} (-1)^k f_k\), and the deep reason that
\(\chi\) is invariant — the Euler-Poincaré theorem — connects it to
homology groups. These ideas lie ahead.
Kuratowski's Theorem and Graph Minors
Euler's formula gives necessary conditions for planarity (edge bounds), but not
sufficient ones — a graph can satisfy \(E \leq 3V - 6\) and still be non-planar. The complete
characterization of planarity is one of the jewels of graph theory.
Subdivisions
Definition: Subdivision
A subdivision of a graph \(H\) is any graph obtained by replacing
edges of \(H\) with paths — that is, inserting degree-2 vertices along edges.
If \(G\) contains a subgraph that is a subdivision of \(H\), we say \(G\) contains
an \(H\)-subdivision (or an \(H\)-topological minor).
Subdivisions preserve planarity: inserting degree-2 vertices into a planar drawing does not
create crossings, and removing them does not eliminate crossings. Thus, a graph containing
a \(K_5\)- or \(K_{3,3}\)-subdivision cannot be planar.
Theorem: Kuratowski's Theorem (1930)
A graph \(G\) is planar if and only if it contains no subdivision of \(K_5\) and no
subdivision of \(K_{3,3}\).
The "only if" direction is clear: \(K_5\) and \(K_{3,3}\) are non-planar, and subdivisions
preserve non-planarity. The "if" direction is deep: the standard proof reduces to
edge-minimal non-planar graphs (those that are non-planar but become planar upon deletion
of any single edge), shows that any such graph must be 3-connected, and then uses a
careful case analysis on the structure around a chosen edge to extract either a
\(K_5\)- or \(K_{3,3}\)-subdivision. The technical execution of this case analysis is the
substantive content of Kuratowski's original argument and lies beyond our present scope.
Kuratowski's theorem characterizes planarity in terms of forbidden substructures, but does
not immediately yield an efficient algorithm. The algorithmic question — given \(G\), determine
whether it is planar and construct an embedding if so — admits a linear-time \(O(V)\)
solution via the Hopcroft-Tarjan planarity testing algorithm, based on depth-first search.
Graph Minors
Definition: Minor
A graph \(H\) is a minor of \(G\), written \(H \preceq G\), if \(H\) can be
obtained from \(G\) by a sequence of:
- Edge deletion: removing an edge.
- Vertex deletion: removing a vertex and all its incident edges.
- Edge contraction: merging the two endpoints of an edge into a
single vertex (any resulting parallel edges or loops are removed to maintain simplicity).
A graph property is minor-closed if whenever \(G\) has the property
and \(H \preceq G\), then \(H\) also has the property.
Definition: Branch Set and Branch Vertex
Suppose \(H\) is a minor of \(G\) with \(V(H) = \{h_1, \ldots, h_n\}\). The sequence
of contractions and deletions producing \(H\) from \(G\) determines, for each
\(h_i \in V(H)\), a non-empty connected subgraph \(B_i \subseteq G\) — the set of
all vertices of \(G\) that are eventually contracted into \(h_i\). The subgraphs
\(B_1, \ldots, B_n\) are pairwise vertex-disjoint and are called the
branch sets of the minor; the vertex \(h_i\) of \(H\) is the
branch vertex corresponding to \(B_i\). For each edge \(h_i h_j \in E(H)\),
there is at least one edge of \(G\) joining a vertex of \(B_i\) to a vertex of \(B_j\)
(the edge of \(G\) that survived contraction to become \(h_i h_j\)).
Planarity is minor-closed: deleting vertices/edges in a plane graph trivially preserves
planarity, and contracting an edge can be realized by sliding its two endpoints together
along the edge arc within the same plane embedding. The minor relation is more general
than the subdivision relation (every topological minor is a minor, but not conversely),
leading to an equivalent characterization.
Theorem: Wagner's Theorem (1937)
A graph \(G\) is planar if and only if it has no \(K_5\) minor and no \(K_{3,3}\) minor.
Proof sketch:
The "only if" direction follows from minor-closure: if \(G\) had \(K_5\) or \(K_{3,3}\)
as a minor, planarity of \(G\) would imply that minor is itself planar, contradicting
non-planarity of \(K_5\)
and \(K_{3,3}\).
For the "if" direction, we reduce to
Kuratowski's theorem via the
following relation between minors and subdivisions. Suppose \(G\) has a \(K_n\)-minor
with branch sets
\(B_1, \ldots, B_n\). For \(K_{3,3}\) (where \(n = 6\) and the maximum vertex degree
is 3), each \(B_i\) needs to send edges to only 3 other branch sets, so we can pick
a representative vertex in each \(B_i\) and connect representatives via
internally-disjoint paths inside the branch sets — this directly yields a
\(K_{3,3}\)-subdivision in \(G\). For
\(K_5\) (maximum vertex degree 4), the same construction works when each branch set
sends edges to all 4 others through 4 distinct internal points, producing a
\(K_5\)-subdivision; otherwise, some branch set has a more concentrated connection
pattern, and a careful rerouting yields a \(K_{3,3}\)-subdivision instead. In either
case, \(G\) contains a \(K_5\)- or \(K_{3,3}\)-subdivision, and Kuratowski's
characterization completes the argument.
Wagner's theorem can be viewed as an instance of a far more general phenomenon:
Theorem: Robertson-Seymour Graph Minor Theorem (2004)
In any infinite sequence of graphs \(G_1, G_2, G_3, \ldots\), there exist indices \(i < j\)
such that \(G_i\) is a minor of \(G_j\). Equivalently, every minor-closed graph property
is characterized by a finite set of forbidden minors.
A full proof of the Robertson-Seymour theorem is far beyond the scope of this page;
it relies on deep tools from structural graph theory including tree-decompositions and
well-quasi-ordering of graph classes (a property stating that the ordering admits
neither an infinite descending chain nor an infinite antichain — for the minor relation
on finite graphs, the absence of infinite descending chains is automatic, so the
substantive content lies in ruling out infinite antichains). For planarity, the finite
forbidden set is simply \(\{K_5, K_{3,3}\}\). For other surfaces, the forbidden minor
sets are larger but still finite. This theorem guarantees that every minor-closed graph
property has a finite combinatorial certificate.
Subgraph Patterns and GNN Expressivity
The detection of subgraph patterns is central to the expressivity of
Graph Neural Networks (GNNs). The classical Weisfeiler-Leman (WL)
isomorphism test — which upper-bounds the distinguishing power of message-passing
GNNs — cannot distinguish certain non-isomorphic graphs that differ only in their
subgraph structure. Higher-order WL tests and equivariant architectures improve expressivity
by tracking \(k\)-tuples of vertices, effectively detecting richer local patterns.
The graph minor and subdivision relations provide a natural vocabulary for describing
the structural motifs that distinguish graphs, and understanding which such motifs
a network can and cannot detect is a frontier question in geometric deep learning.
Dual Graphs and the Bridge to Higher Dimensions
We return to the plane embedding itself. A planar embedding reveals not only the
graph \(G\) but also a dual structure that interchanges vertices and faces —
a perspective that opens the door to higher-dimensional generalizations. This duality
is a recurring motif in mathematics — from dual spaces
in functional analysis to Poincaré duality in algebraic topology. Here, we see its
combinatorial incarnation.
The Dual Graph
Note on multigraphs. Although our standing convention restricts to
simple graphs, the dual construction below produces in general a multigraph —
self-loops arise from bridge edges, and parallel edges arise from pairs of faces sharing
multiple bordering edges. Throughout this section we work in the slightly broader category
of plane multigraphs; the spanning-tree proof of Euler's formula extends to this setting
without modification.
Definition: Dual Graph
Let \(G\) be a connected plane (multi)graph. The dual graph \(G^*\) is constructed as follows:
- Place one vertex of \(G^*\) inside each face of \(G\).
- For each edge \(e\) of \(G\), draw an edge of \(G^*\) crossing \(e\) and connecting
the two faces that \(e\) borders.
The dual satisfies \(V(G^*) = F(G)\), \(E(G^*) = E(G)\), and \(F(G^*) = V(G)\).
Notice that the vertex-face duality swaps the roles of \(V\) and \(F\) while preserving \(E\).
Applying Euler's formula to \(G^*\): \(V(G^*) - E(G^*) + F(G^*) = F - E + V = 2\),
confirming that the formula is self-dual.
Proposition: Double Dual
For a connected plane (multi)graph \(G\), \((G^*)^* \cong G\).
Proof sketch:
The dual operation is involutive. Each face \(f\) of \(G\) becomes a vertex
\(v_f\) of \(G^*\). When we form \((G^*)^*\), the vertices \(v_f\) of \(G^*\) define
an embedding whose faces correspond to the original vertices of \(G\): each vertex
\(v\) of \(G\) is surrounded by faces of \(G\) (the faces incident to \(v\)), whose
corresponding \(G^*\)-vertices form a cycle around \(v\) — and this cycle bounds a
face of \(G^*\) containing \(v\) in its interior. Reading off the dual once more
recovers a vertex at each such face, producing exactly the vertices of \(G\).
The bijection on edges follows similarly: each edge \(e\) of \(G\) is crossed by a
unique edge \(e^*\) of \(G^*\), and \(e^*\) is in turn crossed by a unique edge of
\((G^*)^*\), namely \(e\) itself.
Duality is Cleaner on the Sphere
On the plane, the dual construction has a small asymmetry: the outer face of \(G\)
becomes a single vertex of \(G^*\), and when we redraw \((G^*)^*\) we must again
designate one face as the outer face — a choice that does not affect isomorphism
type but does break visual symmetry. The cleanest setting for self-duality is the
sphere \(S^2 = \mathbb{R}^2 \cup \{\infty\}\), where the distinction between
bounded and unbounded faces disappears. There, all faces are topologically
equivalent disks, and the dual operation is genuinely involutive without any
choice of "outer" face. This is the first hint that planar graph theory is
really sphere graph theory wearing a disguise — a perspective that becomes
essential when generalizing to higher-genus surfaces.
The dual graph captures complementary structural information. If \(T\) is a spanning tree
of \(G\), then the edges of \(G^*\) corresponding to \(E(G) \setminus E(T)\) form a
spanning tree of \(G^*\) — a result known as the tree-cotree decomposition.
This complementary tree principle connects tree
enumeration (Cayley's formula, Kirchhoff's matrix tree theorem from
Trees & Enumeration) to
the dual perspective. In 3D computer vision, triangle meshes have a natural dual where
each triangular face becomes a vertex; convolution operations on this dual graph process
face-level data (such as surface normals), complementing vertex-level message passing in
graph neural networks.
The f-Vector Perspective
We now introduce notation that anticipates the higher-dimensional generalization. Define the
f-vector of a plane graph \(G\) as the triple
\[
f = (f_0, f_1, f_2) = (V, E, F).
\]
Euler's formula becomes the alternating sum
\[
f_0 - f_1 + f_2 = 2.
\]
For a simplicial complex \(K\) of dimension \(d\), the f-vector is
\((f_0, f_1, \ldots, f_d)\) where \(f_k\) counts the \(k\)-simplices, and the Euler
characteristic is \(\chi(K) = \sum_{k=0}^{d} (-1)^k f_k\). Euler's formula for
plane graphs is the \(d = 2\) case of this general pattern.
Beyond the Plane: Surface Embeddings
Every planar graph can be drawn on the sphere \(S^2\) without crossings (project from
the plane to the sphere, placing the outer face around the north pole), and conversely.
More interesting is what happens when we embed graphs on surfaces of higher genus.
Proof sketch:
The argument extends the spanning-tree induction from the
planar case. The cellular
hypothesis ensures that each face is a disk, so the operation of adding a non-tree
edge \(e\) splits a single face into two disk-shaped faces (the same Jordan-arc
argument as in the planar proof, applied within each individual face). Hence the
alternating sum \(V - E + F\) is invariant under edge additions to a fixed cellular
embedding, just as in the planar case.
The base value, however, is \(\chi(\Sigma_g) = 2 - 2g\) rather than \(2\). This can
be seen from the cellular structure of \(\Sigma_g\) itself: build the genus-\(g\)
surface by attaching \(g\) handles to the sphere, and observe that each handle
attachment removes 2 disks (faces) and replaces them with a single cylinder,
decreasing \(F\) by 2 while leaving \(V\) and \(E\) unchanged. Starting from the
sphere's value \(\chi(\Sigma_0) = 2\) (the planar formula, viewed on \(S^2\)),
we obtain \(\chi(\Sigma_g) = 2 - 2g\).
For the sphere (\(g = 0\)), \(\chi = 2\) — recovering the planar formula. For the torus
(\(g = 1\)), \(\chi = 0\). For the double torus (\(g = 2\)), \(\chi = -2\). As we add
handles, the Euler characteristic decreases by 2 each time, reflecting the increasing
topological complexity of the surface.
This has a concrete consequence: under cellular embedding, the edge bound
\(E \leq 3V - 6\) becomes \(E \leq 3V + 6(g - 1)\) on \(\Sigma_g\), allowing more edges.
For example, the complete graph \(K_7\) — which has \(E = 21\) and violates the planar bound
\(3(7) - 6 = 15\) — can be embedded on the torus (\(g = 1\)), where the bound is
\(3(7) + 6(0) = 21\). And indeed, \(K_7\) embeds on the torus.
From Surfaces to Simplicial Complexes
A graph embedded on a surface is intrinsically a 2-dimensional object: it has
vertices (dimension 0), edges (dimension 1), and faces (dimension 2). To study
these higher-dimensional structures systematically — without the crutch of a specific
embedding surface — we need a purely combinatorial language for "shapes of any
dimension." This is precisely what simplicial complexes provide.
The oriented edges and face boundaries of a plane graph become special cases of
oriented simplices and the boundary operator, and the
face-counting we performed here generalizes to the full f-vector and Euler characteristic
of an abstract complex.
Graph Coloring
We conclude with one of the most celebrated applications of Euler's formula: the
coloring of planar graphs. A proper \(k\)-coloring of a graph is
an assignment of colors from a palette of \(k\) colors to the vertices such that no
two adjacent vertices share the same color. The minimum \(k\) for which a proper
\(k\)-coloring exists is the chromatic number \(\chi(G)\).
Definition: Proper Coloring and Chromatic Number
A proper \(k\)-coloring of \(G = (V, E)\) is a function
\(c \colon V \to \{1, 2, \ldots, k\}\) such that \(c(u) \neq c(v)\) whenever
\(\{u, v\} \in E\). The chromatic number is
\[
\chi(G) = \min\{k : G \text{ admits a proper } k\text{-coloring}\}.
\]
The chromatic number \(\chi(G)\) is distinct from the Euler characteristic, though
they share the same notation — context always disambiguates. Note that \(\chi(G) \geq \omega(G)\),
where \(\omega(G)\) is the clique number (size of the largest
complete subgraph), since any clique requires all distinct colors.
The Six and Five Color Theorems
We can immediately obtain a weak coloring bound from the degree constraint.
Theorem: Six Color Theorem
Every simple planar graph is 6-colorable: \(\chi(G) \leq 6\).
Proof:
Induct on \(V\). If \(V \leq 6\), color each vertex with a distinct color (using at
most 6 of the 6 available colors). For \(V > 6\), we know \(G\) has a vertex \(v\)
with \(\deg(v) \leq 5\) by the
minimum degree corollary of Euler's formula.
Remove \(v\) and its edges to obtain \(G' = G - v\), which is still planar. (Note:
\(G'\) may be disconnected even if \(G\) is connected, but the theorem statement
does not assume connectivity, so the induction hypothesis applies to \(G'\) directly.)
By the induction hypothesis, \(G'\) is 6-colorable. Since \(v\) has at most 5
neighbors, they use at most 5 colors, so at least one of the 6 colors is available
for \(v\). Restoring \(v\) with this color gives a proper 6-coloring of \(G\).
Improving from 6 to 5 requires a more delicate argument. The key idea is that when
we are short of colors, we can rearrange existing colors to free one up, using
a technique known as a Kempe chain.
Theorem: Five Color Theorem
Every simple planar graph is 5-colorable: \(\chi(G) \leq 5\).
Proof:
Induct on \(V\). The base case \(V \leq 5\) is handled by coloring each vertex with a
distinct color. For the inductive step, let \(v\) be a vertex with \(\deg(v) \leq 5\)
(which exists by the
minimum degree corollary).
If \(\deg(v) \leq 4\), the argument from the Six Color Theorem
works directly — remove \(v\), 5-color \(G - v\), and a color is available for \(v\).
So suppose \(\deg(v) = 5\), and let \(v_1, v_2, v_3, v_4, v_5\) be its neighbors in
clockwise order around \(v\) in the planar embedding. Remove \(v\); by induction,
5-color \(G - v\). If the five neighbors use at most 4 distinct colors, a color is
available for \(v\). So suppose all five colors appear: \(c(v_i) = i\) for \(i = 1, \ldots, 5\).
Define a Kempe chain: for colors \(i\) and \(j\), let \(K_{i,j}\) be the
connected component of the subgraph induced by vertices colored \(i\) or \(j\) that
contains \(v_i\). Consider two cases:
Case 1: \(v_3 \notin K_{1,3}\) — that is, no path of vertices colored
only 1 or 3 connects \(v_1\) to \(v_3\). Swap colors 1 and 3 throughout \(K_{1,3}\).
The swap preserves properness: within the chain, swapping \(1 \leftrightarrow 3\) is
a symmetric relabeling; outside the chain, no vertex adjacent to a chain vertex can
have color 1 or 3 (otherwise it would belong to \(K_{1,3}\) by maximality of the
connected component), so the swap creates no conflict at the chain's boundary. After
the swap, \(v_1\) has color 3 (while \(v_3\), which lies outside \(K_{1,3}\), retains
its color 3). The five neighbors of \(v\) thus carry colors \((3, 2, 3, 4, 5)\),
leaving color 1 free for \(v\).
Case 2: \(v_3 \in K_{1,3}\). Then there exists a path \(P\) from
\(v_1\) to \(v_3\) using only vertices colored 1 or 3. Together with the edges
\(v v_1\) and \(v v_3\), this path forms a simple closed curve \(C\) in the plane.
By the Jordan Curve Theorem, \(C\) separates the plane into an
interior and an exterior.
In the cyclic order \(v_1, v_2, v_3, v_4, v_5\) around \(v\), the vertex \(v_2\) lies
strictly between \(v_1\) and \(v_3\). The edge \(v v_2\) emerges from \(v\) in the
angular sector bounded by the edges \(v v_1\) and \(v v_3\) (which form part of \(C\)),
placing \(v_2\) on one side of \(C\); the edges \(v v_4\) and \(v v_5\) emerge from
\(v\) on the opposite angular sector, placing \(v_4\) and \(v_5\) on the other side.
Therefore any path in \(G\) from \(v_2\) to \(v_4\) must cross \(C\). But the vertices
of \(C\) all have color 1 or 3, so a path consisting only of vertices colored 2 or 4
cannot meet \(C\) — meaning no 2-4 Kempe chain connects \(v_2\) to \(v_4\), and we
are in Case 1 for the pair \((v_2, v_4)\). Swapping colors 2 and 4 in the Kempe chain
\(K_{2,4}\) containing \(v_2\) frees color 2 for \(v\).
The Four Color Theorem
Strengthening the Five Color Theorem from 5 to 4 requires fundamentally new techniques.
The Kempe chain argument that proves the Five Color Theorem cannot be straightforwardly
extended: performing two simultaneous color swaps may create interference between the
chains, a subtlety that does not arise with a single swap.
Theorem: Four Color Theorem (Appel-Haken, 1976)
Every simple planar graph is 4-colorable: \(\chi(G) \leq 4\).
The proof relies essentially on computer assistance. The strategy is to identify
an unavoidable set of configurations — a finite collection such that
every planar graph must contain at least one — and then verify that each configuration
is reducible, meaning its presence in a planar graph implies
4-colorability via a Kempe-chain-style argument on the configuration's neighborhood.
Verifying reducibility for hundreds of configurations is what requires the computer.
The gap between 5 and 4 is striking. The Five Color Theorem admits a one-page proof
using Kempe chains. The Four Color Theorem requires computer verification of a finite
case analysis. This disparity illustrates a recurring theme in combinatorics: small
improvements in bounds can require fundamentally different techniques.
Graph Coloring in Computer Science
Determining the chromatic number of an arbitrary graph is
NP-hard — even deciding whether
\(\chi(G) \leq 3\) is NP-complete. Despite this worst-case intractability, graph coloring
has pervasive applications. In compiler optimization,
register allocation reduces to graph coloring: variables that are simultaneously "live"
share an edge in the interference graph, and colors represent CPU registers.
In scheduling, coloring models conflict avoidance — exams sharing students
cannot occupy the same time slot. In wireless networks, frequency channels
are assigned to transmitters via coloring of the interference graph to avoid signal overlap.
The Four Color Theorem itself guarantees that any map can be printed with just four ink colors,
which can be viewed through the dual graph: countries are vertices, shared borders are edges,
and a proper 4-coloring assigns non-conflicting colors.
Interactive Demo: Planar Graph Coloring