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

⚡ Key Takeaways

One-line statement: A planar graph is one that can be drawn in the plane without edge crossings; for any connected such drawing $V - E + F = 2$ (Euler's formula), and every planar graph can be properly colored with at most four colors (Four-Color Theorem). Key result in words: Vertices minus edges plus faces always equals two for connected planar graphs, and four colors always suffice to color any map so that adjacent regions differ. Where it applies: map coloring, network/circuit layout, polyhedra combinatorics, scheduling, graph algorithms. Who/when: Euler (1750s) for the polyhedral formula; Kempe (1879) and Heawood (1890) for early coloring attempts; Appel & Haken (1976) for the computer-assisted Four-Color proof.

💡 The Core Insight

Planarity is a topological property, but its consequences are counting facts. Euler's formula converts the geometry of a crossing-free drawing into a rigid arithmetic relationship among $V$ , $E$ , and $F$ . From that one equation flows everything: edge bounds ( $E \le 3V-6$ ), the impossibility of embedding $K_5$ and $K_{3,3}$ , the existence of a vertex of degree $\le 5$ , and ultimately the chain of reductions that yields the coloring theorems. The lesson: a global invariant constrains local structure.

DefinitionPlanar Graph and Plane Graph

A graph $G$ is planar if there exists an injective drawing in $\mathbb{R}^2$ (equivalently the sphere $S^2$ ) mapping vertices to distinct points and edges to simple arcs that intersect only at shared endpoints. A specific such drawing is a plane graph (an embedding). The drawing divides the plane into open connected regions called faces; exactly one is unbounded, the outer (infinite) face. For a face $f$ , its degree $\deg(f)$ is the number of edges encountered in a walk around its boundary, counting an edge twice if both its sides touch $f$ (e.g., a bridge).

DefinitionProper Coloring and Chromatic Number

A proper $k$ -coloring of $G$ is a map $c: V \to \{1,\dots,k\}$ with $c(u) \neq c(v)$ whenever $uv \in E$ . The chromatic number $\chi(G)$ is the least $k$ for which a proper $k$ -coloring exists.

TheoremEuler's Polyhedron Formula

For any connected plane graph with $V$ vertices, $E$ edges, and $F$ faces, equation [1] holds. More generally, a plane graph with $c$ connected components satisfies $V - E + F = 1 + c$ .

TheoremKuratowski–Wagner

A graph is planar if and only if it contains no subgraph that is a subdivision of $K_5$ or $K_{3,3}$ (Kuratowski), equivalently no $K_5$ or $K_{3,3}$ minor (Wagner).

TheoremFour-Color Theorem (Appel–Haken, 1976)

Every planar graph $G$ satisfies $\chi(G) \le 4$ . Equivalently, the regions of any plane map can be colored with four colors so that regions sharing a boundary arc receive distinct colors.

TheoremFive-Color Theorem (Heawood, 1890)

Every planar graph satisfies $\chi(G) \le 5$ , with an elementary proof.

ProofEuler's Formula by Induction on Edges

Let $G$ be a connected plane graph. 1. Base case. If $E = V - 1$ , then $G$ is a tree (connected, acyclic). A tree has no cycles, so its drawing bounds no bounded region: $F = 1$ . Then $V - E + F = V - (V-1) + 1 = 2$ . ✓ 2. Inductive step. Suppose [1] holds for all connected plane graphs with fewer than $E$ edges, and let $G$ have $E \ge V$ edges. Then $G$ contains a cycle; pick an edge $e$ lying on a cycle. 3. Because $e$ is on a cycle, it borders two distinct faces. Deleting $e$ merges those two faces into one, so $F$ decreases by 1, $E$ decreases by 1, and $G - e$ is still connected with $V$ vertices. 4. By induction $V - (E-1) + (F-1) = 2$ , which rearranges to $V - E + F = 2$ . ∎

∎

ProofFive-Color Theorem

Induct on $V$ . For $V \le 5$ the claim is trivial. 1. By [3], the average degree is $2E/V \le (6V-12)/V < 6$ , so some vertex $v$ has $\deg(v) \le 5$ . 2. Delete $v$ ; by induction $G - v$ is 5-colorable. Restore $v$ . If its $\le 5$ neighbors use $\le 4$ colors, a free color completes the coloring. 3. The only hard case: $\deg(v) = 5$ and its neighbors $v_1,\dots,v_5$ (in cyclic order) use all five colors, say $c(v_i) = i$ . 4. Consider the subgraph $H_{13}$ induced by colors $1$ and $3$ (a Kempe chain argument). If $v_1$ and $v_3$ lie in different components of $H_{13}$ , swap colors $1\leftrightarrow 3$ in $v_1$ 's component; now color $1$ is free for $v$ . 5. Otherwise a path of alternating colors $1,3$ joins $v_1$ to $v_3$ . Together with $v$ this path encloses one of $v_2$ or $v_4$ . Now consider $H_{24}$ (colors $2$ and $4$ ): the enclosing $1$ – $3$ ring blocks any $2$ – $4$ path between $v_2$ and $v_4$ . So swapping in $v_2$ 's component frees color $2$ for $v$ . ∎

∎

⚠️ Common mistake

The same Kempe-chain idea, applied to a degree-5 vertex aiming for four colors, was Kempe's 1879 "proof" of the four-color theorem. It is wrong. When you must perform two Kempe swaps to free a color, the swaps can interfere, recoloring vertices the first swap relied on. Heawood found this gap in 1890. The gap is exactly why four colors needed a computer-assisted proof, while five colors does not.

mathematician · Leonhard Euler | 1707–1783

The Swiss polymath who, in correspondence around 1750 and in published form in 1752–1758, observed that for convex polyhedra $V - E + F = 2$ . Though Euler did not phrase it graph-theoretically and his proof was incomplete by modern standards (later rigorized by Legendre, Cauchy, and von Staudt), the invariant bears his name and seeds the entire field of combinatorial topology. The same Euler launched graph theory itself with the 1736 Königsberg bridges problem.

🧠 Intuition

Think of Euler's formula on a sphere instead of a plane (stereographic projection makes them equivalent, and on the sphere there is no special "outer" face). Inflate a polyhedron until it becomes a sphere tiled by curved polygons. Now imagine flooding the sphere: start from one face and progressively "burn" the surface. Each time you cross an edge you either enter a new face or close a loop. The bookkeeping of openings and closings is exactly the alternating sum $V - E + F$ , and topology guarantees the surface has "two holes' worth of nothing" — i.e., the sphere's Euler characteristic is $2$ . Change the surface (a torus) and the constant changes to $0$ : that is why the formula is a topological fingerprint of the surface, not of the particular graph.

Figure

A plane embedding of a cube graph: V=8, E=12, F=6 satisfies 8−12+6=2. The golden curve highlights the outer face boundary.

ExampleCounting Faces of a Soccer-Ball Graph

Given: A truncated icosahedron (soccer ball) has 12 pentagonal faces and 20 hexagonal faces meeting 3 at each vertex.

Find: Verify Euler's formula by computing $V$ and $E$ .

Steps:

Faces: $F = 12 + 20 = 32$ .
Edge count via [2]: each pentagon contributes 5 sides, each hexagon 6, each edge shared by two faces:

E = \frac{12\cdot 5 + 20 \cdot 6}{2} = \frac{60 + 120}{2} = 90.

Vertex count: 3 faces meet per vertex, and each face-corner is one (face, vertex) incidence. Total corners $= 12\cdot5 + 20\cdot6 = 180$ , each vertex counted 3 times:

V = \frac{180}{3} = 60.

Check [1]: $V - E + F = 60 - 90 + 32 = 2.$ ✓

Answer: $\boxed{V = 60,\ E = 90,\ F = 32,\ \text{and } V-E+F = 2.}$

ExampleProving

K_5

Is Non-Planar

Given: The complete graph $K_5$ has $V = 5$ vertices and $E = \binom{5}{2} = 10$ edges.

Find: Decide planarity using the edge bound.

Steps:

For a simple planar graph with $V \ge 3$ , inequality [3] requires $E \le 3V - 6$ .
Substitute $V = 5$ : $3(5) - 6 = 9$ .
But $K_5$ has $E = 10 > 9$ .

This violates [3], so no plane embedding can exist.

Answer: $\boxed{K_5 \text{ is non-planar since } 10 > 3(5)-6 = 9.}$ (Note: $K_{3,3}$ has $E=9$ , $V=6$ , so $9 \le 3\cdot6-6 = 12$ passes [3]; you must use the triangle-free bound [4]: $9 > 2\cdot6 - 4 = 8$ , confirming non-planarity.)

⚠️ Common mistake

"Euler's formula needs $V - E + F = 2$ for any graph." No — it requires the graph be connected and drawn planarly without crossings. A disconnected plane graph with $c$ components gives $V - E + F = 1 + c$ . And a graph drawn with crossings does not partition the plane into the right number of faces; you must count faces of an actual embedding.

⚠️ Common mistake

"The Four-Color Theorem says any map needs exactly four colors." It says at most four suffice. Many maps need fewer. Also, the theorem applies to maps where each country is a single connected region sharing boundary arcs (not isolated points). Two regions touching only at a corner are not "adjacent" — the four-color rule allows them the same color.

Counterexample

Why "five colors are sometimes necessary" is false but "more than three are sometimes necessary" is true. No planar map requires five colors (that is the theorem). However, four can genuinely be required: take $K_4$ , the planar graph on four mutually adjacent vertices (a tetrahedron flattened). Every pair is adjacent, so $\chi(K_4) = 4$ . This shows the bound 4 is tight and cannot be lowered to 3 in general.

Counterexample

The torus breaks the constant. Embed $K_5$ — non-planar in the plane — on a torus, where it fits with no crossings. There Euler's formula reads $V - E + F = 0$ , not $2$ , because the torus has Euler characteristic $\chi = 0$ . The Heawood formula then permits up to seven colors on the torus, and seven are sometimes needed (e.g., $K_7$ embeds on the torus).

connection

Planarity sits at the crossroads of several theories. Euler's formula is the genus-0 case of the Euler Characteristic for surfaces, $V - E + F = 2 - 2g$ , tying combinatorics to topology. The edge bound feeds Graph Coloring and the Chromatic Polynomial. The dual notion of a Planar Dual Graph turns face-coloring into vertex-coloring and links map coloring to flows via Tutte Polynomial theory. Kuratowski's theorem is an early instance of the deep Graph Minors Theorem of Robertson–Seymour. Finally, planar graph algorithms underpin Computational Geometry and efficient solvers for problems NP-hard on general graphs.

🔬 Where this appears

⏳ History

- 1736 — Euler solves the Seven Bridges of Königsberg, founding graph theory.

- c. 1750–1758 — Euler states and uses

V - E + F = 2

for convex polyhedra (letters to Goldbach; published in the Novi Commentarii).

- 1813 — Cauchy and (1794/1813) Legendre give more rigorous proofs of the polyhedral formula via projection.

- 1852 — Francis Guthrie poses the four-color conjecture while coloring a map of England; relayed through De Morgan.

- 1879 — Alfred Kempe publishes a "proof" of the four-color theorem using Kempe chains.

- 1890 — Percy Heawood exposes the flaw in Kempe's argument, but salvages it to prove the Five-Color Theorem; introduces the Heawood map-coloring problem for higher-genus surfaces.

- 1930 — Kazimierz Kuratowski characterizes planarity via forbidden subgraphs

K_5

,

K_{3,3}

; Klaus Wagner gives the minor version (1937).

- 1976 — Kenneth Appel and Wolfgang Haken prove the Four-Color Theorem with computer verification of 1,936 reducible configurations — the first major theorem proved with essential computer aid.

- 1997 / 2005 — Robertson, Sanders, Seymour, Thomas give a cleaner reproof (633 configurations); Georges Gonthier produces a fully machine-checked proof in the Coq proof assistant.

open-problem

The four-color theorem is settled, but its texture leaves deep questions. (1) A "human-readable" proof. No fully traditional, surveyable proof avoiding massive case analysis is known; whether one exists is philosophically and mathematically open. (2) Hadwiger's Conjecture, a vast generalization, asserts that every graph with no $K_{t}$ minor is $(t-1)$ -colorable; the case $t=5$ is equivalent to the four-color theorem (Wagner), but $t \ge 7$ remains unproven and is considered one of the central open problems in graph theory. (3) Higher surfaces. The Heawood bound $\chi \le \lfloor (7 + \sqrt{24g+1})/2 \rfloor$ for genus $g \ge 1$ was proved tight (Ringel–Youngs, 1968) for all orientable surfaces except the plane — ironically the sphere/plane case (which the formula would give as 4) is precisely the hard one that needed Appel–Haken.

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

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also