Folioby Interconnected
Log InSign Up

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.

FO
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 K4​ 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.

1
2
3
4

Once the number of vertices reaches 5 (K5​) or the connectivity pattern becomes sufficiently entangled (K3,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 K4​ 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+Fdoes 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≥3 vertices,
E≤3V−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, 3F≤2E, i.e., F≤2E/3. Substituting into Euler's formula:
V−E+32E​≥2⟹E≤3V−6.
Example 8 (Proving thatK5​is not planar).
For K5​: V=5, E=10. But 3V−6=9<10=E, so K5​ cannot be planar.
Theorem 9 (Edge bound for bipartite planar graphs).
A bipartite planar graph satisfies E≤2V−4 (because the absence of triangles strengthens the face bound to 4F≤2E).
Example 10 (Proving thatK3,3​is not planar).
K3,3​ is bipartite with V=6 and E=9. But 2V−4=8<9=E, so K3,3​ cannot be planar.

4. Kuratowski's theorem – a complete characterization of planarity

We have just shown that K5​ and K3,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 K5​ or K3,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:

  1. Five objects are all mutually connected (K5​-type obstruction).

  2. Three objects of one kind are all connected to three objects of another kind (K3,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≤3V−6 implies E=O(V): planar graphs are inherently sparse. For general graphs, E can be as large as O(V2).

Remark 14 (Consequences for running time).
Many graph algorithms have running times expressed as O(V+E) or O(ElogV). On planar graphs, since E=O(V):

  • BFS, DFS: O(V+E)=O(V)

  • Dijkstra (with a heap): O(ElogV)=O(VlogV)

  • Algorithms that run in O(V2) 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 2n/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)≤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)≤5.
Remark 19 (Sketch of the five-color theorem).
The bound E≤3V−6 guarantees that every planar graph contains a vertex of degree at most 5 (since the average degree is 2E/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≤3V−6 ensures that planar graphs are sparse, making algorithms faster.

  • Kuratowski's theorem: K5​ and K3,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 TheoryMathematicsBetween the LinesPlanar GraphsFour Color TheoremKuratowski's Theorem
FO
Folio Official

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

1 followers·107 articles
Graph Theory — Between the LinesPart 8 of 8
Previous
The magic of bipartite graphs — Why everything works
No next article

Share your expertise with the world

Write articles with LaTeX support, build your audience, and earn from your knowledge.

Start Writing — It's Free

More from Folio Official

Folio Official·March 1, 2026

What the max-flow min-cut theorem is really saying — Duality in action

The maximum flow through a network equals the minimum capacity of a cut separating source from sink. This elegant duality is one of the most beautiful results in combinatorics. We develop intuition through water pipes, augmenting paths, and LP duality.

Graph TheoryMathematicsBetween the Lines
Folio Official·March 1, 2026

Why does the greedy algorithm work for trees? — What matroids reveal

Kruskal's algorithm for minimum spanning trees is absurdly simple: sort the edges by weight and add the cheapest one that does not create a cycle. Why does this greedy strategy produce an optimal solution? The answer lies in the cut property and, more deeply, in matroids.

Graph TheoryMathematicsBetween the Lines
Folio Official·March 1, 2026

Why are trees special? — The beauty of minimal connectivity

Seven equivalent characterizations of trees all say the same thing from different angles: a tree is a connected graph with zero redundancy. Add one edge and a cycle appears; remove one edge and the graph disconnects. This article unpacks the beauty behind that knife-edge structure.

Graph TheoryMathematicsBetween the Lines
Folio Official·March 1, 2026

The magic of bipartite graphs — Why everything works

The absence of odd cycles is a single structural property, yet it makes matching, coloring, and covering all tractable at once. This article explores the remarkable power of bipartiteness through König's theorem, Hall's marriage theorem, and the reduction patterns they enable.

Graph TheoryMathematicsBetween the Lines