Planar graphs and Euler's formula (intro) - Discrete Math

SECTION 1

Historical Context & Motivation

The study of planar graphs is one of the oldest threads in combinatorics, predating the formal definition of a graph by more than a century. The question at its core is deceptively simple: given a network of nodes and connections, can you draw it flat on a sheet of paper so that no two edges cross? This geometric constraint has deep algebraic consequences, most famously captured by Euler's formula relating vertices, edges, and faces. Understanding planarity is not merely an aesthetic exercise; it underpins circuit-board layout, geographic information systems, and the topological classification of surfaces.

1736 • Königsberg Bridge Problem

Leonhard Euler solved the famous Seven Bridges of Königsberg problem, founding graph theory and establishing the concept of an Eulerian path. His analysis introduced the combinatorial style of reasoning that would later yield his polyhedral formula.

1750 • Euler's Polyhedral Formula

In a letter to Christian Goldbach, Euler stated the relation V − E + F = 2 for convex polyhedra. Although his original proof had gaps, the result became a cornerstone of topology and was later extended to planar graphs.

1852 • The Four-Color Conjecture

Francis Guthrie conjectured that every planar map can be colored with at most four colors so that no two adjacent regions share a color. This conjecture, proven in 1976, highlighted the central importance of planarity in graph coloring.

1930 • Kuratowski's Theorem

Kazimierz Kuratowski provided an elegant characterization: a graph is planar if and only if it contains no subdivision of K₅ or K₃,₃. This gave the first complete algebraic criterion for planarity.

1974 • Linear-Time Planarity Testing

Hopcroft and Tarjan devised the first O(n) algorithm for deciding whether a graph is planar, making planarity testing efficient enough for large-scale applications in VLSI design and network visualization.

From Euler's initial insight about polyhedra to modern algorithms that test planarity in linear time, the central question has remained: what structural properties distinguish graphs that can be embedded in the plane from those that cannot? This lesson introduces the foundational definitions, the celebrated formula V − E + F = 2, and the techniques used to verify and apply planarity in discrete mathematics.

SECTION 2

Core Principles & Definitions

Before exploring Euler's formula, we need precise language for the objects involved. A graph G = (V, E) consists of a finite set V of vertices and a set E of edges, each connecting two vertices. When we ask whether G is planar, we are asking whether there exists a drawing of G in the Euclidean plane ℝ² such that edges meet only at their shared endpoints — no crossings occur in the interior of any edge. Such a crossing-free drawing is called a planar embedding (or plane graph). Crucially, planarity is an intrinsic property of the abstract graph, not of any particular drawing; a graph is planar if at least one valid embedding exists, even if many other drawings have crossings.

Planar Graph

A graph that can be drawn in the plane with no edge crossings. The graph itself is planar; the specific drawing realizing this property is a planar embedding.

Face (Region)

In a planar embedding, the edges and vertices divide the plane into connected regions called faces. Exactly one face is unbounded — the outer (infinite) face. All others are bounded.

Euler's Formula

For any connected planar graph with V vertices, E edges, and F faces: V − E + F = 2. This invariant holds regardless of which valid embedding you choose.

Edge Bound

A simple planar graph on V ≥ 3 vertices satisfies E ≤ 3V − 6. This inequality, derived from Euler's formula, provides a quick non-planarity test: any graph violating it cannot be planar.

Kuratowski's Criterion

A graph is planar if and only if it contains no subgraph that is a subdivision of K₅ (complete graph on 5 vertices) or K₃,₃ (complete bipartite graph on 3 + 3 vertices). These are the two minimal non-planar obstructions.

✦

KEY TAKEAWAY

Think of a planar embedding like flattening a wire-frame sculpture onto a table without any wires crossing. The enclosed regions — the holes in the wire mesh — are the faces. No matter how you flatten the same sculpture (provided no wires cross), Euler's formula guarantees that the combination V − E + F always equals 2. It is a topological invariant: stretching, bending, or reshaping the drawing changes nothing about the count.

SECTION 3

Visual Explanation — Planar Embeddings & Faces

The diagram below shows two drawings of the same graph. On the left, edges cross — this is merely a bad drawing, not evidence of non-planarity. On the right, the same graph is redrawn so that no edges cross, revealing the faces of a valid planar embedding. The outer (infinite) face surrounds the entire drawing, while three bounded faces appear as enclosed regions.

Left: a drawing of a graph where two diagonal edges cross — this does not mean the graph is non-planar. Right: the same graph redrawn as a valid planar embedding with faces f₁, f₂, f₃ (bounded) and f₄ (the outer, unbounded face). Verify Euler's formula: V − E + F = 5 − 7 + 4 = 2.

Notice that in the planar embedding, every edge borders exactly two faces (though the same face may appear on both sides of a bridge — an edge whose removal disconnects the graph). The degree of a face is the number of edge-sides bounding it, counted with multiplicity. The sum of all face degrees equals 2E, since each edge contributes exactly two face-boundary incidences. This observation is the combinatorial engine behind many corollaries of Euler's formula.

SECTION 4

Mathematical Framework

Euler's formula can be proved by induction on the number of edges. We begin with a connected planar graph G having V vertices, E edges, and F faces in some fixed embedding. The proof builds the graph edge by edge and shows that the quantity V − E + F is invariant throughout the construction.

EULER'S FORMULA FOR CONNECTED PLANAR GRAPHS

V − E + F = 2

V = number of vertices, E = number of edges, F = number of faces (including the unbounded outer face). The graph must be connected. For a graph with k connected components, the formula generalizes to V − E + F = 1 + k.

Proof Sketch (Induction on E)

Base case. A connected graph with E = 0 is a single vertex: V = 1, F = 1 (only the outer face). So V − E + F = 1 − 0 + 1 = 2. ✓

Inductive step. Assume the formula holds for all connected planar graphs with fewer than E edges. Pick any edge e of G. There are two cases. Case 1: e is a bridge (its removal disconnects G). Removing e reduces V − E + F by 0 − 1 + (−1) = 0 (one fewer edge, one fewer face, but the graph splits into two components which we handle via the generalized formula). Re-combining yields the invariant. Case 2: e lies on a cycle. Removing e merges two faces into one, so F decreases by 1, E decreases by 1, and V stays the same: V − (E − 1) + (F − 1) = V − E + F. The invariant is preserved.

EDGE UPPER BOUND (SIMPLE GRAPHS)

E ≤ 3V − 6 (V ≥ 3)

Derived from Euler's formula by noting every face has degree ≥ 3, so 2E ≥ 3F. Substituting F = 2 − V + E gives 2E ≥ 3(2 − V + E) = 6 − 3V + 3E, hence E ≤ 3V − 6. A graph violating this inequality cannot be planar.

EDGE BOUND FOR TRIANGLE-FREE PLANAR GRAPHS

E ≤ 2V − 4 (V ≥ 3, no 3-cycles)

If G has no triangles, every face has degree ≥ 4, so 2E ≥ 4F. The same substitution yields E ≤ 2V − 4. This sharper bound is often used to show that K₃,₃ is non-planar.

⚠

Why K₅ and K₃,₃ fail

For K₅: V = 5, E = 10. The bound gives E ≤ 3(5) − 6 = 9 < 10. Violation — K₅ is non-planar. For K₃,₃: V = 6, E = 9. The general bound gives E ≤ 3(6) − 6 = 12, which is satisfied; however, K₃,₃ is triangle-free, so we use the sharper bound E ≤ 2(6) − 4 = 8 < 9. Violation — K₃,₃ is non-planar.

SECTION 5

Planar vs. Non-Planar — Key Examples

Developing intuition for planarity requires examining a gallery of canonical examples. The complete graphs K₁ through K₄ are all planar (K₄ is the tetrahedral graph), while K₅ is the smallest complete graph that is not. Among complete bipartite graphs, K₂,₃ is planar but K₃,₃ is not. The Petersen graph, a workhorse of counterexamples in graph theory, is likewise non-planar — it contains a K₃,₃ subdivision.

Four canonical examples. K₄ and K₂,₃ admit planar embeddings and satisfy Euler's formula. K₅ violates E ≤ 3V − 6 and K₃,₃ violates E ≤ 2V − 4 (the triangle-free bound), confirming both are non-planar.

Graph	V	E	Applicable Bound	Planar?
K₄	4	6	E ≤ 3(4) − 6 = 6 ✓	Yes
K₅	5	10	E ≤ 3(5) − 6 = 9 ✗	No
K₂,₃	5	6	E ≤ 3(5) − 6 = 9 ✓	Yes
K₃,₃	6	9	E ≤ 2(6) − 4 = 8 ✗ (triangle-free)	No
Petersen	10	15	E ≤ 2(10) − 4 = 16 ✓ (but contains K₃,₃ subdivision)	No

Planarity status of selected graphs with edge-bound analysis

An important subtlety is visible in the Petersen graph row: the edge bound E ≤ 3V − 6 (or its triangle-free variant) is a necessary condition for planarity, not a sufficient one. A graph may satisfy the bound yet still be non-planar because it contains a K₅ or K₃,₃ subdivision. The edge bound is a quick filter; Kuratowski's theorem (or its equivalent, Wagner's theorem) provides the definitive criterion.

SECTION 6

Worked Example — Applying Euler's Formula

Consider a connected, simple, planar graph G with 8 vertices and 12 edges. We want to determine how many faces its planar embedding has and verify that the edge bound is satisfied.

Finding the Number of Faces

1
Step 1 — Identify Given Values

We are told that G is a connected, simple, planar graph. The given quantities are V = 8 (vertices) and E = 12 (edges). We seek F, the number of faces in any planar embedding.

V = 8, E = 12, F = ?
2
Step 2 — Check the Edge Bound

Before applying Euler's formula, we verify that planarity is at least consistent with the edge bound. For a simple planar graph with V ≥ 3: E ≤ 3V − 6. Substituting: 12 ≤ 3(8) − 6 = 18. Since 12 ≤ 18, the bound is satisfied. This does not prove planarity, but it is consistent with the assumption.

12 ≤ 18 ✓ — edge bound satisfied
3
Step 3 — Apply Euler's Formula

Since G is connected and planar, Euler's formula V − E + F = 2 holds. Substituting the known values: 8 − 12 + F = 2. Solving for F: F = 2 − 8 + 12 = 6.

F = 6
4
Step 4 — Interpret the Result

The planar embedding of G has 6 faces. One of these is the unbounded outer face, so there are 5 bounded faces. Since the sum of face degrees equals 2E = 24, the average face degree is 24 / 6 = 4. This means the faces are, on average, quadrilateral — which is typical of moderately dense planar graphs.

5 bounded faces + 1 outer face = 6 total; average face degree = 4

SECTION 7

Strengths & Limitations of the Edge-Bound Test

Euler's formula and its corollary edge bounds are among the most useful first-pass tools in graph theory, but they have well-defined limitations. Understanding when these tools succeed and when they fall short is essential for choosing the right approach to a planarity question.

Aspect	Strengths	Limitations
Speed	O(1) arithmetic check — just count V and E.	Cannot identify specific obstructing subgraphs.
Conclusiveness	If E > 3V − 6, the graph is definitively non-planar.	If E ≤ 3V − 6, the graph may or may not be planar (necessary but not sufficient).
Generality	Works for all simple graphs; a triangle-free variant exists.	Fails for dense but planar graphs (e.g., maximal planar with E = 3V − 6 exactly).
Face counting	Euler's formula gives F exactly once planarity is established.	Does not reveal the structure or shapes of individual faces.
Sufficiency for non-planarity	Handles K₅ and most dense non-planar graphs immediately.	Misses sparse non-planar cases like the Petersen graph — Kuratowski's theorem is needed.

Edge-bound test: strengths vs. limitations

✦

KEY TAKEAWAY

Think of the edge bound E ≤ 3V − 6 as a metal detector at a security checkpoint: if it beeps (the bound is violated), you know for certain that something is wrong — the graph is non-planar. But if it stays silent, the graph merely might be safe. You still need a deeper inspection (Kuratowski's or Wagner's theorem, or a planarity algorithm) to certify that no hidden obstruction exists.

SECTION 8

Connection to Advanced Theory

Euler's formula for planar graphs is actually the tip of a topological iceberg. When we embed graphs on surfaces other than the plane — the torus, the projective plane, or surfaces of higher genus — the formula generalizes beautifully. The Euler characteristic χ of a surface S is a topological invariant, and for a connected graph embedded on S, Euler's formula becomes V − E + F = χ(S). The plane (or equivalently the sphere) has χ = 2; the torus has χ = 0; a surface of genus g has χ = 2 − 2g.

Concept	Introductory (This Lesson)	Advanced Extension
Formula	V − E + F = 2 (plane/sphere)	V − E + F = χ(S) for surface S of genus g
Non-planarity criterion	Kuratowski: no K₅ or K₃,₃ subdivision	Robertson–Seymour theorem: finite set of forbidden minors for each surface
Coloring	Four-Color Theorem (planar graphs)	Heawood conjecture: χ(G) ≤ ⌊(7 + √(49 − 24χ)) / 2⌋ for surfaces of genus ≥ 1
Edge bound	E ≤ 3V − 6	E ≤ 3(V − χ(S)) for triangulations on surface S
Duality	Dual graph of a planar embedding	Dual graphs on arbitrary surfaces; matroid duality

From planar graphs to topological graph theory

Beyond topology, planarity has deep connections to graph minor theory. Wagner's theorem rephrases Kuratowski's result in terms of minors rather than subdivisions: G is planar if and only if it has no K₅ minor and no K₃,₃ minor. The Robertson–Seymour graph minor theorem extends this idea spectacularly, proving that every minor-closed family of graphs is characterized by a finite set of forbidden minors. Planarity, then, is just the first chapter in a vast structural theory of graphs on surfaces.

SECTION 9

Practice Problems

Question 1: CONCEPTUAL

Explain why a tree on n vertices is always planar. How many faces does its planar embedding have? Justify your answer using Euler's formula.

Show answer

A tree on n vertices has exactly n − 1 edges and no cycles. Since there are no cycles, every drawing of a tree is crossing-free — you can lay out the tree in the plane without any edges intersecting. By Euler's formula, F = 2 − V + E = 2 − n + (n − 1) = 1. The single face is the unbounded outer face. Intuitively, with no cycles there are no enclosed regions, confirming F = 1.

Question 2: BASIC CALCULATION

A connected planar graph has 10 vertices and 15 edges. How many faces does its planar embedding have? Is the graph maximal planar (a triangulation)?

Show answer

By Euler's formula: F = 2 − V + E = 2 − 10 + 15 = 7. To check whether the graph is a triangulation, we compute the maximum number of edges: E_max = 3V − 6 = 3(10) − 6 = 24. Since 15 < 24, the graph is not maximal planar. Equivalently, in a triangulation every face has degree 3, so 2E = 3F, giving E = 3F/2 = 3(7)/2 = 10.5, which is not an integer and does not equal 15 — confirming that not all faces are triangles.

Question 3: INTERMEDIATE

A simple, connected, planar graph G has 12 vertices, every face in its embedding is a quadrilateral (degree 4), and every vertex has the same degree d. Determine E, F, and d.

Show answer

Since every face has degree 4, the face-degree sum gives 4F = 2E, so F = E/2. Substituting into Euler's formula: 12 − E + E/2 = 2, which simplifies to 12 − E/2 = 2, giving E = 20 and F = 10. The vertex-degree sum gives dV = 2E, so d(12) = 2(20) = 40, yielding d = 10/3. Since d must be a positive integer, we recheck: actually d = 40/12 is not an integer. Let's recalculate: 12d = 40, so d = 10/3, which is not integral. This means no such regular quadrilateral-faced planar graph on 12 vertices exists. The problem illustrates that Euler's formula can serve as a disproof tool — the derived parameters must all be consistent. If we instead had V = 8, we would get E = 12, F = 6, d = 3, which is realized by the cube graph Q₃.

Question 4: APPLIED

A circuit board connects 20 components (vertices) with 54 wires (edges). The design engineer claims the board can be manufactured on a single layer (planar layout). Use the edge bound to evaluate this claim.

Show answer

For a simple planar graph with V ≥ 3, the edge bound is E ≤ 3V − 6. Here V = 20 and E = 54. Compute 3(20) − 6 = 54. Since 54 ≤ 54, the bound is satisfied with equality. This means the graph could, in principle, be planar — specifically, it would need to be a maximal planar graph (triangulation). However, satisfying the edge bound does not guarantee planarity; the engineer should run a planarity testing algorithm (e.g., Boyer–Myrvold) to confirm. If it is planar, Euler's formula gives F = 2 − 20 + 54 = 36, and every face would be a triangle (since 2E = 108 = 3 × 36 = 3F).

Question 5: CRITICAL THINKING

Prove that every simple planar graph has at least one vertex of degree at most 5. (Hint: use the edge bound and the handshaking lemma.)

Show answer

Suppose, for contradiction, that every vertex has degree ≥ 6. By the handshaking lemma, 2E = Σ deg(v) ≥ 6V, so E ≥ 3V. But the edge bound for simple planar graphs requires E ≤ 3V − 6 < 3V. This is a contradiction, so our assumption is false: at least one vertex must have degree ≤ 5. This result is fundamental — it is the starting point for the proof that every planar graph is 6-colorable (and, with more work, 5-colorable). The Four-Color Theorem strengthens this further but requires a far more involved argument. The existence of a low-degree vertex also provides the basis for an inductive proof of the five-color theorem via the technique of removing a vertex of degree ≤ 5 and coloring the reduced graph.

SUMMARY

Summary

A planar graph is one that can be drawn in the plane with no edge crossings. Any such crossing-free drawing is a planar embedding, and its edges partition the plane into connected regions called faces, including one unbounded outer face. Euler's formula — V − E + F = 2 — holds for every connected planar graph and serves as the master equation from which key corollaries follow, notably the edge bound E ≤ 3V − 6 for simple graphs and E ≤ 2V − 4 for triangle-free graphs.

These bounds provide quick non-planarity tests: any graph violating them is definitively non-planar. However, passing the edge bound is necessary but not sufficient. The definitive criterion is Kuratowski's theorem: a graph is planar if and only if it contains no subdivision of K₅ or K₃,₃. Looking ahead, Euler's formula generalizes to graphs embedded on arbitrary surfaces via the Euler characteristic V − E + F = χ(S), linking combinatorial graph theory to topology and the rich landscape of graph minor theory.