What does the shape of a graph determine? — From planarity to the four-color theorem

Planar graphs are sparse ($E \leq 3V - 6$), and many problems that are hard on general graphs become tractable when planarity is assumed. This article covers Euler's formula, Kuratowski's theorem, and the philosophical significance of the four-color theorem.

Folio Official

March 1, 2026

Throughout this series, we have treated graphs as purely combinatorial objects – sets of vertices and edges. But graphs also have a geometric dimension. Whether a graph can be drawn in the plane without edge crossings – its planarity– turns out to determine a surprising amount.

1 Planar graphs

Definition 1 (Planar graph).

A graph

G

is planar if it can be drawn in the plane so that no two edges cross except possibly at a common endpoint. A specific such drawing is called a plane graph.

Example 2.

The complete graph

K_{4}

is planar. If you imagine a tetrahedron and "open up" one face to form the outer boundary, you obtain a crossing-free drawing in the plane.

Once the number of vertices reaches 5 ( $K_{5}$ ) or the connectivity pattern becomes sufficiently entangled ( $K_{3, 3}$ ), a crossing-free drawing is no longer possible.

2 Euler's formula – a topological invariant

The most fundamental property of plane graphs is Euler's formula.

Theorem 3 (Euler's formula).

For a connected plane graph with

V

vertices,

E

edges, and

F

faces,

V - E + F = 2.

Example 4.

A plane drawing of

K_{4}

has

V = 4

E = 6

, and

F = 4

(three triangular faces plus the outer face), giving

4 - 6 + 4 = 2

Remark 5 (What makes Euler's formula remarkable).

The astonishing feature of this formula is that the quantity

V - E + F

does not depend on the particular drawing. No matter how the same planar graph is embedded in the plane,

V - E + F = 2

holds.

In the language of topology,

V - E + F

is the Euler characteristic, a topological invariant. The value 2 reflects the Euler characteristic of the sphere (or, equivalently, the plane with a point at infinity).

On the torus (the surface of a doughnut), the corresponding formula becomes

V - E + F = 0

. The notion of "faces" depends on the surface on which the graph is drawn.

3 Edge bound for planar graphs – guaranteed sparsity

Euler's formula imposes a strong constraint on how many edges a planar graph can have.

Theorem 6 (Edge bound for planar graphs).

In a simple connected planar graph with

V \geq 3

vertices,

E \leq 3 V - 6.

Remark 7 (Derivation).

Every face of a simple plane graph is bounded by at least 3 edges (no loops or multi-edges). Since each edge borders exactly 2 faces,

3 F \leq 2 E

, i.e.,

F \leq 2 E /3

. Substituting into Euler's formula:

V - E + \frac{2 E}{3} \geq 2 ⟹ E \leq 3 V - 6.

Example 8 (Proving that

K_{5}

is not planar).

For

K_{5}

V = 5

E = 10

. But

3 V - 6 = 9 < 10 = E

, so

K_{5}

cannot be planar.

Theorem 9 (Edge bound for bipartite planar graphs).

A bipartite planar graph satisfies

E \leq 2 V - 4

(because the absence of triangles strengthens the face bound to

4 F \leq 2 E

Example 10 (Proving that

K_{3, 3}

is not planar).

K_{3, 3}

is bipartite with

V = 6

and

E = 9

. But

2 V - 4 = 8 < 9 = E

, so

K_{3, 3}

cannot be planar.

4 Kuratowski's theorem – a complete characterization of planarity

We have just shown that $K_{5}$ and $K_{3, 3}$ are not planar using edge-counting arguments. Kuratowski proved that these two are the only obstructions to planarity.

Theorem 11 (Kuratowski's theorem).

A graph

G

is non-planar if and only if it contains a subgraph that is a subdivision of

K_{5}

K_{3, 3}

Definition 12 (Subdivision).

A subdivision of a graph

H

is the graph obtained by replacing some of the edges of

H

with internally disjoint paths.

Remark 13.

In intuitive terms, there are only two reasons a graph can fail to be planar:

Five objects are all mutually connected ( $K_{5}$ -type obstruction).
Three objects of one kind are all connected to three objects of another kind ( $K_{3, 3}$ -type obstruction – also known as the "three utilities" problem).

Every non-planar graph, no matter how large or complex, reduces to one of these two patterns.

5 Planarity makes computation easier

The bound $E \leq 3 V - 6$ implies $E = O (V)$ : planar graphs are inherently sparse. For general graphs, $E$ can be as large as $O (V^{2})$ .

Remark 14 (Consequences for running time).

Many graph algorithms have running times expressed as

O (V + E)

O (E lo g V)

. On planar graphs, since

E = O (V)

BFS, DFS: $O (V + E) = O (V)$
Dijkstra (with a heap): $O (E lo g V) = O (V lo g V)$
Algorithms that run in $O (V^{2})$ on general graphs may run in $O (V)$ on planar graphs.

Beyond running-time improvements, some NP-complete problems become tractable on planar graphs.

Theorem 15 (Planar separator theorem).

Every

n

-vertex planar graph can be partitioned into two parts, each of size at most

2 n /3

, by removing

O (n)

vertices.

This separator theorem enables divide-and-conquer strategies, yielding sub-exponential algorithms and polynomial-time approximation schemes (PTAS) for many problems on planar graphs.

6 The four-color theorem – a 150-year quest

The most famous result about planar graph coloring is the four-color theorem.

Theorem 16 (Four-color theorem (Appel–Haken, 1976)).

Every planar graph can be properly colored with at most 4 colors:

χ (G) \leq 4

Remark 17 (The philosophical significance of the four-color theorem).

The four-color conjecture was posed in 1852 and resisted proof for 124 years. When a proof finally arrived, it relied on a computer-assisted case analysis involving over 1,000 configurations – a proof that no human can read and verify in its entirety.

This raised profound questions for the philosophy of mathematics:

Should a proof that depends on a computer be accepted as a proof?
Does a proof that humans cannot understand carry mathematical meaning?

The mathematical community ultimately accepted the proof, but the search for a more elegant, human-readable argument continues to this day.

That four colors suffice is deep and non-trivial, but the weaker statement that five colors suffice is comparatively straightforward.

Theorem 18 (Five-color theorem).

Every planar graph can be properly colored with at most 5 colors:

χ (G) \leq 5

Remark 19 (Sketch of the five-color theorem).

The bound

E \leq 3 V - 6

guarantees that every planar graph contains a vertex of degree at most 5 (since the average degree is

2 E / V < 6

). Remove this vertex and apply induction. When reinserting it, at most 5 neighbors use at most 5 colors, so a valid color always exists.

Getting from 5 down to 4 requires a more delicate technique: Kempe chains, which allow colors to be swapped along alternating-color paths. Kempe himself published a "proof" of the four-color theorem using this method in 1879, but eleven years later Heawood discovered a flaw. (Heawood also showed that Kempe's argument, while insufficient for four colors, does correctly establish the five-color theorem.)

7 Takeaway

A planar graph is one that can be drawn in the plane without edge crossings.
Euler's formula $V - E + F = 2$ is the fundamental topological invariant of plane graphs.
The bound $E \leq 3 V - 6$ ensures that planar graphs are sparse, making algorithms faster.
Kuratowski's theorem: $K_{5}$ and $K_{3, 3}$ subdivisions are the only obstructions to planarity.
The four-color theorem: every planar graph is 4-colorable (proved with computer assistance).

This concludes the eight-article "Between the Lines" series on graph theory. From the bridges of Kö

Graph Theory Mathematics Between the Lines

Folio Official

Mathematics "between the lines" — exploring the intuition textbooks leave out, written in LaTeX on Folio.

1 フォロワー·105 記事

What does the shape of a graph determine? — From planarity to the four-color theorem

1 Planar graphs

2 Euler's formula – a topological invariant

3 Edge bound for planar graphs – guaranteed sparsity

4 Kuratowski's theorem – a complete characterization of planarity

5 Planarity makes computation easier

6 The four-color theorem – a 150-year quest

7 Takeaway

あなたの専門知識を世界に発信しよう

Folio Officialの他の記事

Monetizing Your Articles — How to Earn Revenue Safely with Stripe Connect

Mastering Theorem Environments — theorem, definition, proof, and Friends

Combinatorial Designs and Latin Squares: Balanced Arrangements

Burnside's Lemma and P\'olya Enumeration: Counting Under Symmetry