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

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.

A planar graph $G = (V, E)$ is a graph admitting an embedding in the Euclidean plane in which edges meet only at shared endpoints. Such an embedding partitions the plane into connected faces, and Euler's formula relates the counts of vertices, edges, and faces by the invariant $V - E + F = 2$ for connected graphs. This deceptively simple identity is one of the cornerstones of combinatorial topology and forces strong structural constraints — for instance, it immediately bounds the number of edges and guarantees a vertex of small degree, which in turn drives every coloring argument. The most famous consequence is the Four-Color Theorem: any planar map can be colored with four colors so that adjacent regions receive distinct colors. A surprising fact: although the five-color theorem has a clean half-page proof, the four-color theorem resisted for over a century and was finally proved only with the aid of a computer checking nearly 1,500 configurations.

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 \leq 3 V - 6$ ), the impossibility of embedding $K_{5}$ and $K_{3, 3}$ , the existence of a vertex of degree $\leq 5$ , and ultimately the chain of reductions that yields the coloring theorems. The lesson: a global invariant constrains local structure.

Formal Statement

Planar Graph and Plane Graph

A graph $G$ is planar if there exists an injective drawing in $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 $de g (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).

Proper 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 $χ (G)$ is the least $k$ for which a proper $k$ -coloring exists.

The central numerical relations:

V - E + F = 2 (connected plane graph)

⟳Build

G

edge by edge from a spanning tree; each new edge either closes a cycle (+1 face) or extends a path, preserving the alternating sum.

v \in V \sum de g (v) = 2 E, f \in F \sum de g (f) = 2 E

⟳Each edge contributes 2 to the vertex-degree total (one per endpoint) and 2 to the face-degree total (one per side).

E \leq 3 V - 6 (V \geq 3)

⟳Each face has degree

\geq 3

, so

2 E = \sum de g (f) \geq 3 F

; substitute

F = 2 - V + E

and solve.

E \leq 2 V - 4 (triangle-free, V \geq 3)

⟳Same as [3] but each face now has degree

\geq 4

, giving

2 E \geq 4 F

Euler'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$ .

Kuratowski–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).

Four-Color Theorem (Appel–Haken, 1976)

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

Five-Color Theorem (Heawood, 1890)

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

Why It Holds / Derivation

Euler's Formula by Induction on Edges

Let $G$ be a connected plane graph.

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$ . ✓

Inductive step. Suppose [1] holds for all connected plane graphs with fewer than $E$ edges, and let $G$ have $E \geq V$ edges. Then $G$ contains a cycle; pick an edge $e$ lying on a cycle.

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.

By induction $V - (E - 1) + (F - 1) = 2$ , which rearranges to $V - E + F = 2$ . ∎

Five-Color Theorem

Induct on $V$ . For $V \leq 5$ the claim is trivial.

By [3], the average degree is $2 E / V \leq (6 V - 12) / V < 6$ , so some vertex $v$ has $de g (v) \leq 5$ .

Delete $v$ ; by induction $G - v$ is 5-colorable. Restore $v$ . If its $\leq 5$ neighbors use $\leq 4$ colors, a free color completes the coloring.

The only hard case: $de g (v) = 5$ and its neighbors $v_{1}, \dots, v_{5}$ (in cyclic order) use all five colors, say $c (v_{i}) = i$ .

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$ .

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$ . ∎

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.

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.

Building 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.

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.

Worked Examples

Counting 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 \cdot 5 + 20 \cdot 6 = 180$ , each vertex counted 3 times:

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

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

Answer:

V = 60, E = 90, F = 32, and V - E + F = 2.

Proving $K_5$ Is Non-Planar

Given: The complete graph

K_{5}

has

V = 5

vertices and

E = (2 5) = 10

edges. Find: Decide planarity using the edge bound. Steps:

For a simple planar graph with $V \geq 3$ , inequality [3] requires $E \leq 3 V - 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:

K_{5} is non-planar since 10 > 3 (5) - 6 = 9.

(Note: $K_{3, 3}$ has $E = 9$ , $V = 6$ , so $9 \leq 3 \cdot 6 - 6 = 12$ passes [3]; you must use the triangle-free bound [4]: $9 > 2 \cdot 6 - 4 = 8$ , confirming non-planarity.)

Common Misconceptions

"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. "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. 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

χ (K_{4}) = 4

. This shows the bound 4 is tight and cannot be lowered to 3 in general. 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

χ = 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).

Connections

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 - 2 g$ , 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.

Real-World Applications

VLSI / PCB layout. Routing wires without crossings on a single layer is exactly a planarity test; non-planar nets force extra layers or vias.
Map and GIS coloring. Cartographers and chart software use four (or fewer) colors to distinguish adjacent administrative regions.
Register allocation / scheduling. Conflict graphs that happen to be planar (or near-planar) admit fast coloring heuristics bounded by the four-color guarantee.
Mesh processing & finite elements. Euler's formula validates triangulations of surfaces and bounds the number of triangles given vertices, used in CAD and graphics.
Frequency assignment. Assigning non-interfering channels to transmitters is graph coloring; geographically planar interference graphs benefit from the small chromatic bound.
Road-network and circuit testing. Planarity-based algorithms (Hopcroft–Tarjan linear-time test) detect crossings in transport or chip networks.
Polyhedral chemistry (fullerenes). Counting pentagon/hexagon faces of carbon cages like C $_{60}$ uses exactly the Euler-formula bookkeeping in the soccer-ball example.

Historical Development

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.

Subtleties & Limits

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 \geq 7$ remains unproven and is considered one of the central open problems in graph theory. (3) Higher surfaces. The Heawood bound $χ \leq ⌊(7 + 24 g + 1) /2 ⌋$ for genus $g \geq 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.