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.

💡 The Core Insight

Core Insight: Planar graphs satisfy rigid combinatorial constraints encoded by Euler's Formula (V−E+F=2V - 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.

Definition

Planar Graph: A graph G=(V,E)G = (V, E) is planar if there exists a drawing of GG in the plane R2\mathbb{R}^2 (called a planar embedding) such that:

  • Each vertex v∈Vv \in V is mapped to a distinct point in the plane
  • Each edge e∈Ee \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 VV vertices, EE edges, and FF faces:

V−E+F=2V - 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)≤4\chi(G) \leq 4 for all planar graphs GG.

Core Theory

TheoremEuler's Formula

Theorem [1]: Let GG be a connected plane graph with VV vertices, EE edges, and FF faces. Then:

V−E+F=2V - E + F = 2

Theorem [2] (Consequences of Euler's Formula): For a connected planar graph GG with V≥3V \geq 3 vertices and EE edges: 1. E≤3V−6E \leq 3V - 6 2. If GG is triangle-free, then E≤2V−4E \leq 2V - 4 3. GG 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 GG is planar, then χ(G)≤4\chi(G) \leq 4.

Proof

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

Base case: If E=0E = 0, then GG is a single vertex (since GG is connected), so V=1V = 1, F=1F = 1 (only the exterior face), and V−E+F=1−0+1=2V - E + F = 1 - 0 + 1 = 2. ✓

Inductive step: Assume the formula holds for all connected plane graphs with fewer than EE edges. Consider a connected plane graph GG with E≥1E \geq 1 edges. Case 1: GG is a tree. Then GG has no cycles, so E=V−1E = V - 1 (property of Trees). Since GG is a tree embedded in the plane with no cycles, it has only one face (the exterior). Thus F=1F = 1, and:

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

Case 2: GG contains a cycle. Choose any edge ee that belongs to a cycle. Since ee is on a cycle, it borders exactly two distinct faces. Remove ee to obtain a graph G′G'. The graph G′G' is still connected (since ee was part of a cycle, alternative paths exist between its endpoints). The graph G′G' has:

  • V′=VV' = V (same vertices)
  • E′=E−1E' = E - 1 (one fewer edge)
  • F′=F−1F' = F - 1 (the two faces separated by ee merge into one)

By the inductive hypothesis, V′−E′+F′=2V' - E' + F' = 2, so:

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

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

Proof of Theorem [2.1]: We prove E≤3V−6E \leq 3V - 6 for V≥3V \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:

2E≥3F2E \geq 3F

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

2E≥3(2−V+E)2E \geq 3(2 - V + E)
2E≥6−3V+3E2E \geq 6 - 3V + 3E
3V−6≥E3V - 6 \geq E

Therefore E≤3V−6E \leq 3V - 6. □

Proof of Theorem [2.3]: Suppose for contradiction that every vertex has degree at least 6. By the Handshaking Lemma, ∑vdeg⁡(v)=2E\sum_{v} \deg(v) = 2E, so:

2E≥6V2E \geq 6V
E≥3VE \geq 3V

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

∎
⚠️ Common mistake

Common Misconception: Not all graphs can be drawn in the plane! For instance, the complete graph K5K_5 (5 vertices all connected) and the complete bipartite graph K3,3K_{3,3} are non-planar. The bound E≤3V−6E \leq 3V - 6 proves K5K_5 is non-planar: it has V=5V = 5 and E=10E = 10, but 3(5)−6=9<103(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 kk connected components, the formula becomes V−E+F=1+kV - E + F = 1 + k.

mathematician

<a class="wiki-link" href="/wiki/leonhard-euler">Leonhard Euler</a> (1752) — Discovered the fundamental relationship V−E+F=2V - E + F = 2 while studying polyhedra, establishing the foundation for both graph theory and algebraic topology.

visualization

Planar vs Non-Planar Graphs K₄ (Planar) V=4, E=6, F=4 4-6+4=2 ✓ K₅ (Non-Planar) V=5, E=10 E > 3V-6 10 > 9 ✗

Examples and Applications

Example1

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=8V = 8
  • Edges: The 12 edges of the cube: E=12E = 12
  • Faces: When embedded in the plane, the cube has 6 square faces plus 1 exterior face: F=7F = 7

Wait! Actually, in a planar embedding of the cube graph, one face becomes the "outside." The correct count is F=6F = 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=6F = 6

Verification:

V - E + F = 8 - 12 + 6 = 2$$ ✓ **Maximum edges**: Does this graph saturate the bound $E \leq 3V - 6$? $$3(8) - 6 = 18

Since E=12<18E = 12 < 18, the cube graph has fewer edges than the maximum possible for a planar graph with 8 vertices.

Example2

Proving K5K_5 is Non-Planar The complete graph K5K_5 has 5 vertices with every pair connected.

  • V=5V = 5
  • E=(52)=10E = \binom{5}{2} = 10

Claim: K5K_5 cannot be drawn in the plane without edge crossings.

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

E≤3V−6E \leq 3V - 6
10≤3(5)−6=910 \leq 3(5) - 6 = 9

This is a contradiction! Therefore, K5K_5 is non-planar.

Alternative approach using faces: If K5K_5 were planar, by Euler's Formula:

F=2−V+E=2−5+10=7F = 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 2E≥3F2E \geq 3F, giving:

20≥2120 \geq 21

Contradiction! This confirms K5K_5 is non-planar.

Counterexample

Why Connectedness Matters in Euler's Formula Consider a graph GG consisting of two disjoint triangles embedded in the plane:

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

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

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

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

V−E+F=1+kV - E + F = 1 + k

Here k=2k = 2, so 6−6+3=3=1+26 - 6 + 3 = 3 = 1 + 2. ✓ This shows that the connectedness hypothesis in Theorem [1] cannot be dropped.

🧠 Intuition

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: EE increases by 1, FF increases by 1, so V−E+FV - E + F stays constant.
  • If the edge creates a new vertex (subdividing an existing edge), then both VV and EE increase by 1, keeping V−E+FV - 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=0V - E + F = 0, while on a sphere (topologically equivalent to the plane via Stereographic Projection), we also get V−E+F=2V - 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=2V - 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 K5K_5 or K3,3K_{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

connection

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 gg (number of "handles"), the Euler characteristic is χ=V−E+F=2−2g\chi = V - E + F = 2 - 2g. The plane and sphere have genus 0, giving χ=2\chi = 2. A torus has genus 1, giving χ=0\chi = 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≥1g \geq 1 requires at most ⌊7+1+48g2⌋\lfloor \frac{7 + \sqrt{1 + 48g}}{2} \rfloor colors, except the Klein bottle which requires 6.

What You Need First

What This Opens Up

See Also

Graph Theory · Kuratowski's Theorem · Euler Characteristic · Graph Coloring · Trees · Dual Graphs · Polyhedra