Planar Graphs, Euler's Formula, and the Four-Color Theorem

Planar graphs can be drawn on a plane without edge crossings; Euler's Formula (V - E + F = 2) governs their structure
The Four-Color Theorem states any planar graph/map needs at most 4 colors so adjacent regions don't share colors
Euler's Formula constrains edge density: planar graphs have at most 3V - 6 edges, limiting their complexity
The Four-Color Conjecture (1852) resisted proof for 124 years until Appel & Haken's 1976 computer-assisted verification
Planar graphs bridge discrete graph theory and topology through the Euler Characteristic invariant
Königsberg bridge problem (1736) sparked graph theory; systematic study emerged from 19th-century map coloring

Planar Graphs, Euler's Formula, and the Four-Color Theorem

Overview

A planar graph is a graph that can be drawn on the plane without any of its edges crossing. This seemingly simple geometric constraint gives rise to profound mathematical relationships and one of the most famous problems in mathematics. The study of planar graphs sits at the intersection of Graph Theory, Topology, and Combinatorics, revealing deep connections between discrete structures and continuous spaces.

The history of planar graphs begins with Leonhard Euler's solution to the Königsberg bridge problem in 1736, often considered the birth of graph theory itself. However, the systematic study of planar graphs emerged in the 19th century when mathematicians began investigating map coloring. The observation that any map can apparently be colored with just four colors so that no adjacent regions share the same color led to the Four-Color Conjecture, posed around 1852. This innocent-looking problem would resist mathematical proof for over a century, finally yielding in 1976 to a computer-assisted proof by Appel and Haken.

Euler's Formula, discovered in 1752, provides the fundamental relationship governing planar graphs: for any connected planar graph, the number of vertices minus edges plus faces equals 2. This elegant formula not only constrains the structure of planar graphs but also connects discrete graph theory to the Euler Characteristic in topology, demonstrating that combinatorial and topological invariants can coincide. The formula serves as the cornerstone for proving the Four-Color Theorem and understanding the limitations of planar representations.

Core Insight: Planar graphs satisfy rigid combinatorial constraints encoded by Euler's Formula (

V - E + F = 2

), which bounds their edge density and ultimately proves that every planar graph can be colored with at most four colors—a topological constraint masquerading as a combinatorial one. Planar Graph: A Graph Theory|graph

G = (V, E)

is planar if there exists a drawing of

G

in the plane

R^{2}

(called a planar embedding) such that:

Each vertex $v \in V$ is mapped to a distinct point in the plane
Each edge $e \in E$ is mapped to a continuous curve connecting its endpoints
No two edges intersect except possibly at their common endpoints

A plane graph is a specific planar embedding of a planar graph. Such an embedding divides the plane into connected regions called faces. One face is unbounded (the exterior face or infinite face).

Euler's Formula: For a connected plane graph with

V

vertices,

E

edges, and

F

faces:

V - E + F = 2

Four-Color Theorem: Every planar graph is 4-colorable, meaning its vertices can be assigned colors from a set of four colors such that no two adjacent vertices receive the same color. Equivalently, the Chromatic Number

χ (G) \leq 4

for all planar graphs

G

Core Theory

Euler's Formula

Theorem [1]: Let

G

be a connected plane graph with

V

vertices,

E

edges, and

F

faces. Then:

V - E + F = 2

Theorem [2] (Consequences of Euler's Formula): For a connected planar graph

G

with

V \geq 3

vertices and

E

edges:

$E \leq 3 V - 6$
If $G$ is triangle-free, then $E \leq 2 V - 4$
$G$ has at least one vertex of degree at most 5

Theorem [3] (Four-Color Theorem): Every planar graph has chromatic number at most 4: if

G

is planar, then

χ (G) \leq 4

. Proof of Theorem [1] (Euler's Formula) by induction on the number of edges: Base case: If

E = 0

, then

G

is a single vertex (since

G

is connected), so

V = 1

F = 1

(only the exterior face), and

V - E + F = 1 - 0 + 1 = 2

. ✓ Inductive step: Assume the formula holds for all connected plane graphs with fewer than

E

edges. Consider a connected plane graph

G

with

E \geq 1

edges. Case 1: $G$ is a tree. Then

G

has no cycles, so

E = V - 1

(property of Trees). Since

G

is a tree embedded in the plane with no cycles, it has only one face (the exterior). Thus

F = 1

, and:

V - E + F = V - (V - 1) + 1 = 2

Case 2: $G$ contains a cycle. Choose any edge

e

that belongs to a cycle. Since

e

is on a cycle, it borders exactly two distinct faces. Remove

e

to obtain a graph

G^{'}

The graph $G^{'}$ is still connected (since $e$ was part of a cycle, alternative paths exist between its endpoints). The graph $G^{'}$ has:

$V^{'} = V$ (same vertices)
$E^{'} = E - 1$ (one fewer edge)
$F^{'} = F - 1$ (the two faces separated by $e$ merge into one)

By the inductive hypothesis, $V^{'} - E^{'} + F^{'} = 2$ , so:

V - (E - 1) + (F - 1) = 2

V - E + F = 2

By induction, Euler's Formula holds for all connected plane graphs. □

Proof of Theorem [2.1]: We prove

E \leq 3 V - 6

for

V \geq 3

Each face is bounded by at least 3 edges (since we have no loops or multiple edges in a simple graph). If we sum the number of edge-face incidences, each edge borders exactly 2 faces, so:

2 E \geq 3 F

From Euler's Formula, $F = 2 - V + E$ . Substituting:

2 E \geq 3 (2 - V + E)

2 E \geq 6 - 3 V + 3 E

3 V - 6 \geq E

Therefore $E \leq 3 V - 6$ . □

Proof of Theorem [2.3]: Suppose for contradiction that every vertex has degree at least 6. By the Handshaking Lemma,

\sum_{v} de g (v) = 2 E

, so:

2 E \geq 6 V

E \geq 3 V

But this contradicts $E \leq 3 V - 6$ for $V \geq 3$ . Therefore, some vertex has degree at most 5. □

Common Misconception: Not all graphs can be drawn in the plane! For instance, the complete graph

K_{5}

(5 vertices all connected) and the complete bipartite graph

K_{3, 3}

are non-planar. The bound

E \leq 3 V - 6

proves

K_{5}

is non-planar: it has

V = 5

and

E = 10

, but

3 (5) - 6 = 9 < 10

. Similarly, many students think Euler's Formula applies to any graph drawing, but it specifically requires a planar embedding with no crossings. Also, the formula assumes connectedness—for a graph with

k

connected components, the formula becomes

V - E + F = 1 + k

. Leonhard Euler (1752) — Discovered the fundamental relationship

V - E + F = 2

while studying polyhedra, establishing the foundation for both graph theory and algebraic topology.

Examples and Applications

1

Verifying Euler's Formula for a Cube Graph

Consider the graph of a cube, which is planar. We can draw it in the plane as follows:

Vertices: The 8 corners of the cube: $V = 8$
Edges: The 12 edges of the cube: $E = 12$
Faces: When embedded in the plane, the cube has 6 square faces plus 1 exterior face: $F = 7$

Wait! Actually, in a planar embedding of the cube graph, one face becomes the "outside." The correct count is

F = 6

(5 visible square faces when you "unfold" one face to infinity, plus the exterior).

Let's recalculate: For a proper planar embedding of the cube graph:

The interior of the plane shows 5 square regions
The exterior (unbounded) face corresponds to the 6th face of the cube
Total faces: $F = 6$

Verification:

V - E + F = 8 - 12 + 6 = 2

✓

Maximum edges: Does this graph saturate the bound

E \leq 3 V - 6

3 (8) - 6 = 18

Since

E = 12 < 18

, the cube graph has fewer edges than the maximum possible for a planar graph with 8 vertices.

2

Proving $K_{5}$ is Non-Planar

The complete graph $K_{5}$ has 5 vertices with every pair connected.

$V = 5$
$E = (2 5) = 10$

Claim:

K_{5}

cannot be drawn in the plane without edge crossings. Proof: Assume

K_{5}

is planar. Then by Theorem [2.1], we must have:

E \leq 3 V - 6

10 \leq 3 (5) - 6 = 9

This is a contradiction! Therefore, $K_{5}$ is non-planar.

Alternative approach using faces: If

K_{5}

were planar, by Euler's Formula:

F = 2 - V + E = 2 - 5 + 10 = 7

Each face requires at least 3 edges on its boundary, and each edge borders exactly 2 faces, so $2 E \geq 3 F$ , giving:

20 \geq 21

Contradiction! This confirms $K_{5}$ is non-planar.

Why Connectedness Matters in Euler's Formula

Consider a graph $G$ consisting of two disjoint triangles embedded in the plane:

$V = 6$ (3 vertices per triangle)
$E = 6$ (3 edges per triangle)
$F = 4$ (one interior face per triangle, plus 2 exterior faces... wait!)

Actually, there's only one exterior face that surrounds both triangles. So $F = 3$ (two triangle interiors plus one shared exterior).

Computing:

V - E + F = 6 - 6 + 3 = 3 \neq = 2

The formula fails because the graph is not connected! For a graph with $k$ components, the generalized Euler formula is:

V - E + F = 1 + k

Here $k = 2$ , so $6 - 6 + 3 = 3 = 1 + 2$ . ✓

This shows that the connectedness hypothesis in Theorem [1] cannot be dropped.

Mental Model: Euler's Formula as a Conservation Law

Think of Euler's Formula as a "conservation law" for planar structures. When you add an edge to a connected planar graph:

If the edge connects two different vertices and creates a new cycle, it splits one face into two: $E$ increases by 1, $F$ increases by 1, so $V - E + F$ stays constant.
If the edge creates a new vertex (subdividing an existing edge), then both $V$ and $E$ increase by 1, keeping $V - E + F$ unchanged.

The constant value of 2 reflects the topological fact that the plane has Euler characteristic 2. Drawing a graph on a torus (donut shape) gives $V - E + F = 0$ , while on a sphere (topologically equivalent to the plane via Stereographic Projection), we also get $V - E + F = 2$ .

Visualizing the Four-Color Theorem: Every planar graph has a vertex of degree ≤ 5 (Theorem 2.3). This means you can always find a "simple" vertex. By repeatedly removing such vertices and coloring them last (using a color different from at most 5 neighbors), you can build a coloring recursively. The hard part—proven with computers—is showing that this greedy strategy, when done carefully, never requires a 5th color.

Historical Development

The study of planar graphs began with Leonhard Euler's 1736 paper on the Seven Bridges of Königsberg, which asked whether one could walk through the city crossing each bridge exactly once. Euler proved it impossible, inventing Graph Theory in the process. His 1752 work on polyhedra led to the formula $V - E + F = 2$ , initially stated for three-dimensional convex polyhedra but naturally extending to planar graphs.

The Four-Color Conjecture emerged around 1852 when Francis Guthrie noticed that he could color a map of English counties with just four colors. The problem was popularized by Augustus De Morgan and later by Arthur Cayley in 1878. The first "proof" by Alfred Kempe in 1879 stood for 11 years before Percy Heawood found a fatal error in 1890. Heawood salvaged a proof of the Five-Color Theorem, establishing that five colors always suffice.

The problem remained open for nearly a century until Kenneth Appel and Wolfgang Haken announced a proof in 1976 using computer verification to check 1,936 unavoidable configurations (later reduced to 633). This was the first major theorem proved with essential computer assistance, sparking philosophical debates about the nature of mathematical proof. The proof was later simplified, and in 2005, Georges Gonthier formalized it completely in the Coq proof assistant, providing the highest level of verification.

Kuratowski's Theorem (1930) gave a beautiful characterization: a graph is planar if and only if it contains no subdivision of

K_{5}

K_{3, 3}

as a subgraph. This connected planarity testing to Matroid Theory and led to efficient algorithms by Hopcroft and Tarjan (1974) for testing planarity in linear time.

Connections to Other Areas

Algebraic Topology and the Euler Characteristic: Euler's Formula for planar graphs is a special case of the Euler Characteristic, a topological invariant. For any CW Complex embedded on a surface of genus

g

(number of "handles"), the Euler characteristic is

χ = V - E + F = 2 - 2 g

. The plane and sphere have genus 0, giving

χ = 2

. A torus has genus 1, giving

χ = 0

. This connects graph embeddings to Algebraic Topology and the Classification of Surfaces. The Heawood Conjecture (proved by Ringel and Youngs in 1968) extends the Four-Color Theorem to all surfaces, showing that a surface of genus

g \geq 1

requires at most

⌊ \frac{7 + 1 + 48 g}{2} ⌋

colors, except the Klein bottle which requires 6.

Planar Graphs, Euler's Formula, and the Four-Color Theorem