Planar Graphs
Throughout Introduction to Graph Theory and the
pages that followed, we treated graphs as purely combinatorial objects, consisting 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 these 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 our study of graphs 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. A graph is
2-connected if it has at least 3 vertices and remains connected after the deletion
of any single vertex. In a simple, 2-connected plane graph, 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)\), which counts 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 it links combinatorics and geometry to topology, as we shall see.
Proof:
Choose any spanning tree
\(T\) of \(G\). Since \(T\) is a tree on \(V\) vertices, it has \(V - 1\) edges by the
characterizations of trees.
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, because 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. First, the
complement of an embedded acyclic graph (such as a spanning tree) is a single connected region,
which justifies \(F = 1\) for \(T\). This rests on the fact that a Jordan arc does not separate
the plane, applied edge by edge along the tree. Second, 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, which justifies \(\Delta F = 1\) at each step. This is the
Jordan Curve Theorem, which states that a simple closed curve in
\(\mathbb{R}^2\) separates the plane into exactly two connected components, an interior and an
exterior. 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\), since each edge contributes 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. Length 1 would require a loop and length 2 a pair of parallel edges, both
excluded by simplicity. The only other closed walk of length 2 traverses a single edge back and
forth, which occurs only when that edge is the whole graph and so \(V = 2\). 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, we obtain
\[
\begin{align*}
2 &= V - E + F \\\\
&\leq V - E + \frac{2}{3}E \\\\
&= V - \frac{1}{3}E,
\end{align*}
\]
which gives \(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, and lengths 1 and 2 are excluded as in the previous proof. Summing gives
\(2E \geq 4F\), so \(F \leq \frac{1}{2}E\). Euler's formula then yields
\[
\begin{align*}
2 &\leq V - E + \frac{1}{2}E \\\\
&= V - \frac{1}{2}E,
\end{align*}
\]
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 \gt 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 \gt 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 \lt 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\). This value depends only on the surface, not on the graph
drawn on it. The sphere \(S^2\), which is topologically equivalent to the plane plus a point at
infinity, has \(\chi = 2\) regardless of how we triangulate it or embed a graph on it.
That invariance is a shadow of a much deeper fact. The Euler characteristic is a
topological invariant, unchanged by continuous deformations
(homeomorphisms). The
alternating sum generalizes to simplicial complexes of arbitrary dimension, and the
Euler-Poincaré theorem, the deep reason that \(\chi\) is invariant,
connects it to homology groups.
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, by 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 crossing-free drawing creates no
crossings, and suppressing such vertices in a crossing-free drawing of a subdivision of \(H\) merges
pairs of arcs into single arcs and yields a crossing-free drawing of \(H\). Since every subgraph of
a planar graph is planar, the same holds for subgraphs. 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, because \(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) and
shows that any such graph must be 3-connected. It 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 asks, given \(G\), to determine
whether it is planar and to construct an embedding if so. This question 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\), whose vertices are exactly the 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 or 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), and this leads 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 this 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 an \(H\)-minor, where \(H\) is
\(K_5\) or \(K_{3,3}\), 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 construction
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 \lt 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 the well-quasi-ordering
of graph classes. A well-quasi-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 upper-bounds the distinguishing power of message-passing GNNs. The test 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, and this perspective opens the
door to higher-dimensional generalizations. 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 is connected and satisfies \(V(G^*) = F(G)\), \(E(G^*) = E(G)\), and \(F(G^*) = V(G)\).
The first two counts are immediate from the construction, and \(G^*\) is connected because any
two faces of \(G\) can be joined by a path of faces that cross edges of \(G\). The third count
is a consequence of Euler's formula applied to the connected plane multigraph \(G^*\), which
gives \(F(G^*) = 2 - V(G^*) + E(G^*) = 2 - F + E = V\). Thus the vertex-face duality swaps the
roles of \(V\) and \(F\) while preserving \(E\), and Euler's formula reads the same for \(G\)
and for \(G^*\).
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 the
faces of \(G\) incident to it. The 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. This choice does not affect the isomorphism type, but it 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. That perspective becomes
essential when we generalize 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
and Kirchhoff's matrix tree theorem) 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. We build the genus-\(g\) surface by attaching
\(g\) handles to the sphere. Each handle attachment removes 2 disk faces and replaces them with
a cylinder. Cutting the cylinder along two arcs that join its two boundary circles at existing
vertices divides it into 2 disk faces, so the attachment leaves \(V\) and \(F\) unchanged while
increasing \(E\) by 2, and the embedding remains cellular. 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\), which recovers 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.
The genus formula has a concrete consequence. For a simple graph with \(V \geq 3\) cellularly
embedded on \(\Sigma_g\), the same face-counting argument turns the edge bound \(E \leq 3V - 6\)
into \(E \leq 3V + 6(g - 1)\), allowing more edges. For example, the complete graph \(K_7\) has
\(E = 21\) and violates the planar bound \(3(7) - 6 = 15\). On the torus (\(g = 1\)) the bound
becomes \(3(7) + 6(0) = 21\), so the count no longer rules \(K_7\) out, 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, with 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 \gt 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, since after
5-coloring \(G - v\) some color remains 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. We remove \(v\) and, 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\).
We now 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\) in 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\).
Hence 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, namely a finite collection such that every
planar graph must contain at least one of them. One then verifies that each configuration is
reducible, meaning that no minimal counterexample to the theorem can contain it.
Any 4-coloring of the smaller graph obtained by removing the configuration extends to the whole
graph, by 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 substantial. 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.
The disparity also raises a deeper question: when a proof requires computer assistance, what does it
mean to trust the proof? That question has its own history, which runs from 1976 to 2005
and reshapes what "proof" itself means in modern mathematics. The history, and its resolution, are
taken up in formal methods.
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. For instance, exams that share 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.
The guarantee is read through the dual graph, in which countries are vertices and shared borders
are edges, so that a proper 4-coloring assigns non-conflicting colors.
Interactive Demo: Planar Graph Coloring
The demo below offers three graphs to color by hand, beginning with \(K_4\). The second is the
icosahedron skeleton, drawn as a genuine plane graph with zero edge crossings, so that the drawing
itself certifies planarity. The third is the Petersen graph, whose non-planarity is certified by an
explicit \(K_{3,3}\) subdivision that can be overlaid on the picture.
The Kempe card turns the Five Color Theorem's proof into a playable move. Once two colors are
chosen, every chain component gains a Swap button. A swap can never create a conflict. The
properness-preservation argument from the proof above is executed by the demo's self-tests before
the demo renders, and the conflict counter confirms it during play. A swap can, however, free a
color exactly where the coloring is stuck. Pressing Stage the proof's move on the
icosahedron reproduces the proof's own predicament: an uncolored vertex whose five neighbors wear
all four colors, one Kempe swap away from rescue.