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 continuous arc connecting \(u\) and \(v\).
- 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\), the faces of the embedding are the connected
regions of \(\mathbb{R}^2 \setminus G\) — that is, the maximal connected components of
the plane after removing all vertices and edges. Exactly one face is unbounded; it is called
the outer face (or infinite face).
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, 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
Leonhard Euler discovered in 1752 that for any connected plane graph, the quantities \(V\),
\(E\), and \(F\) are bound by a remarkable identity. This is one of the most beautiful
results in all of mathematics, connecting combinatorics, geometry, and — as we shall see — topology.
Theorem: Euler's Formula for Planar Graphs
Let \(G\) be a connected plane graph with \(V\) vertices, \(E\) edges, and \(F\) faces. Then
\[
V - E + F = 2.
\]
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\). \(\blacksquare\)
Consequences for Edge Density
Euler's formula constrains how many edges a planar graph can have. The argument hinges on the
observation that every face is bounded by at least 3 edges (in a simple graph with \(V \geq 3\)),
and every edge borders at most 2 faces.
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:
In any plane embedding, each face is bounded by at least 3 edges, and each edge borders at most
2 faces. Counting edge-face incidences: \(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\). \(\blacksquare\)
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:
If \(G\) is triangle-free, every face is bounded by at least 4 edges (a cycle of length
\(\geq 4\)). Then \(2E \geq 4F\), so \(F \leq \frac{1}{2}E\). Euler gives
\(2 \leq V - E + \frac{1}{2}E = V - \frac{1}{2}E\), hence \(E \leq 2V - 4\). \(\blacksquare\)
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\), so assume
\(G\) is connected with \(V \geq 3\). Suppose for contradiction that every vertex
has degree \(\geq 6\). By the
Handshaking Lemma,
\(2E = \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. \(\blacksquare\)
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 — that these are the only obstructions — is
deep and non-trivial. We state it without proof.
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 — was resolved by Hopcroft and Tarjan
(1974), who gave a linear-time \(O(V)\) planarity testing algorithm based on depth-first
search. This remains one of the landmark results in algorithmic graph theory.
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.
A graph property is minor-closed if whenever \(G\) has the property
and \(H \preceq G\), then \(H\) also has the property.
Planarity is minor-closed: deleting vertices/edges and contracting edges in a plane graph
preserves planarity. 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.
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.
The proof of the Robertson-Seymour theorem spans 23 papers published over two decades. 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 "topological" 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
A planar embedding reveals not only the graph itself but also a dual structure
that interchanges vertices and faces. 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
Definition: Dual Graph
Let \(G\) be a connected plane 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 graph \(G\), \((G^*)^* \cong G\).
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^*\). 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.
Theorem: Euler's Formula for Orientable Surfaces
Let \(G\) be a connected graph embedded on an orientable surface \(\Sigma_g\) of genus \(g\)
(a sphere with \(g\) handles). Then
\[
V - E + F = 2 - 2g.
\]
The right-hand side, \(\chi(\Sigma_g) = 2 - 2g\), is the Euler characteristic
of the surface.
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: 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\), the result is trivial. 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. 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\). \(\blacksquare\)
Improving from 6 to 5 requires a more delicate argument due to Alfred Kempe (1879).
The key idea is that when we are short of colors, we can rearrange existing
colors to free one up.
Theorem: Five Color Theorem
Every simple planar graph is 5-colorable: \(\chi(G) \leq 5\).
Proof:
Induct on \(V\). The base case is trivial. For the inductive step, let \(v\) be a vertex
with \(\deg(v) \leq 5\). 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_1\) and \(v_3\) are not connected by a path using
only colors 1 and 3 (i.e., \(v_3 \notin K_{1,3}\)). Then swap colors 1 and 3 in \(K_{1,3}\)
— this is still a proper coloring (the swap preserves properness within the chain and
cannot affect vertices outside it). Now \(v_1\) has color 3, and color 1 is free
for \(v\).
Case 2: \(v_1\) and \(v_3\) are connected by a Kempe chain \(K_{1,3}\).
Then there exists a path \(P\) from \(v_1\) to \(v_3\) using only vertices colored
1 or 3. Since the graph is planar, the closed curve formed by \(P\) together with
the edges \(vv_1\) and \(vv_3\) separates \(v_2\) from \(v_4\) (they lie on opposite
sides, because \(v_1, v_3\) are non-consecutive neighbors of \(v\) in the cyclic
planar order). This means \(v_2\) and \(v_4\) cannot be connected
by a 2-4 Kempe chain (it would have to cross the closed curve, which is impossible
in a planar embedding). So we are in Case 1 for the pair \((v_2, v_4)\): swap colors
2 and 4 in the Kempe chain containing \(v_2\), freeing color 2 for \(v\). \(\blacksquare\)
The Four Color Theorem
Kempe originally claimed in 1879 to have proved the stronger result — that four colors
always suffice. His proof attempted to extend the Kempe chain argument to four colors,
performing two independent color swaps simultaneously. Heawood showed in 1890 that the
first swap can alter the structure of the second Kempe chain, invalidating the argument —
a subtlety that does not arise in the five-color case, where a single swap always suffices.
Heawood salvaged the Five Color Theorem from Kempe's method, but the correct proof
of the Four Color Theorem had to wait nearly a century.
Theorem: Four Color Theorem (Appel-Haken, 1976)
Every simple planar graph is 4-colorable: \(\chi(G) \leq 4\).
The proof by Kenneth Appel and Wolfgang Haken was the first major theorem to rely
essentially on computer assistance. Their strategy was 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 (its presence implies 4-colorability). The verification of
reducibility required checking 1,476 configurations by computer, a calculation that took
over 1,000 hours. A simplified proof by Robertson, Sanders, Seymour, and Thomas (1997)
reduced this to 633 configurations.
The gap between 5 and 4 is vast. The Five Color Theorem is a one-page proof using
Kempe chains. The Four Color Theorem required decades of effort and computer verification.
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