40.04.05 · combinatorics / graph-theory-core

Planar Graphs: Euler's Formula, Kuratowski's and Wagner's Theorems

shipped3 tiersLean: none

Anchor (Master): Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §4.3-§4.6 (Kuratowski's theorem via 3-connected reduction, the algebraic and abstract-dual criteria of Whitney, the structure of 3-connected planar graphs and Whitney's unique-embedding theorem); Mohar-Thomassen 2001 *Graphs on Surfaces* (Johns Hopkins) Ch. 2-3; Ziegler 1995 *Lectures on Polytopes* (Springer GTM 152) Ch. 4 (Steinitz's theorem); the original sources Euler 1758, Kuratowski 1930, Wagner 1937, Whitney 1932-1933, Steinitz 1922

Intuition Beginner

Some graphs can be drawn on a flat sheet of paper with the lines never crossing, and some cannot. A graph that can be drawn this way is called planar. Think of a subway map redrawn so that no two tracks overlap except at stations, or a circuit board where wires must run on one layer without touching. The question "can I draw this without crossings?" is the heart of planarity, and the surprise is that it has a clean answer in terms of two small forbidden patterns.

When you do draw a planar graph without crossings, the lines cut the paper into regions, called faces. One of these regions is the unbounded outside; the rest are the enclosed pockets. Euler noticed a stubborn pattern: count the dots, subtract the lines, add the regions, and you always get the number two, no matter how you draw the graph, as long as it is connected and has no crossings. This single count is one of the oldest and most useful facts in all of graph theory.

Two graphs refuse to be drawn flat. One is the complete graph on five dots, where every dot joins every other; the other is the "three houses, three wells" graph, where three houses each connect to three wells. Try as you might, one crossing is forced. The deep theorem of the subject says these two are the only real obstructions: a graph is planar exactly when it hides no copy of either one inside it.

Visual Beginner

Picture a connected drawing with no crossings and count its three quantities. Take a square with its four corners as dots and its four sides as lines, then add one diagonal. There are four dots and five lines. The diagonal splits the inside of the square into two triangular pockets, and there is the one big outside region, so three faces in all.

The table beside the drawing records the three counts and checks Euler's pattern. Dots minus lines plus faces is $4 - 5 + 3 = 2$ , the value Euler's count always produces for a connected crossing-free drawing.

quantity	count
dots (vertices)	4
lines (edges)	5
faces (regions, including the outside)	3
dots − lines + faces	2

Redraw the same graph any way you like without crossings: bend the lines, move the dots, swap which region is the outside one. The three counts may individually look different in a sloppy drawing, but the dots, lines, and faces still combine to give two.

Worked example Beginner

Use Euler's count to find how many faces a planar drawing has, without drawing it. Suppose a connected graph has $8$ dots and $13$ lines, and you know it can be drawn flat with no crossings. We find the number of faces.

Step 1. Write down Euler's pattern. For a connected crossing-free drawing, dots minus lines plus faces equals two: $v - e + f = 2$ .

Step 2. Put in the numbers you know. Here $v = 8$ and $e = 13$ , so $8 - 13 + f = 2$ .

Step 3. Simplify the left side. $8 - 13 = - 5$ , so the equation is $- 5 + f = 2$ .

Step 4. Solve for the faces. Add five to both sides: $f = 2 + 5 = 7$ . The drawing has seven faces, counting the one unbounded outside region.

Step 5. Sanity-check against the edge limit. A planar graph on $v$ dots can have at most $3 v - 6$ lines once $v$ is at least three. Here $3 \times 8 - 6 = 18$ , and $13$ is below $18$ , so the graph passes the test and could indeed be planar.

What this tells us: once you trust the graph is planar and connected, the face count is forced by the dot and line counts alone. You never had to produce a drawing. The same edge limit, $3 v - 6$ , is the quick test that rules out the two famous non-planar graphs.

Check your understanding Beginner

Formal definition Intermediate+

Topology enters only through one black-box input. A plane graph is a graph drawn in the plane $R^{2}$ (equivalently, the sphere $S^{2}$ ) so that vertices are distinct points, each edge is a simple arc joining its endpoints, distinct edges meet only at shared endpoints, and no edge passes through a vertex it is not incident to ^{[Diestel 2017 §4.1]}. A graph is planar if it is isomorphic to some plane graph; a fixed drawing is a plane embedding. The faces of a plane graph $G$ are the connected regions of $R^{2} ∖ G$ (the plane with the drawing removed); exactly one face is unbounded, the outer face. Write $f$ for the number of faces. The boundary of a face is the set of edges and vertices incident to it; in a $2$ -connected plane graph every face boundary is a cycle. The single topological fact used is the Jordan curve theorem: a simple closed curve in the plane separates it into exactly two regions, an inside and an outside, each having the curve as its full boundary ^{[Mohar-Thomassen 2001 Ch. 2]}.

Definition (subdivision and topological minor). A subdivision of $H$ replaces each edge of $H$ by an internally disjoint path; $H$ is a topological minor of $G$ , written $H ≼_{top} G$ , if $G$ contains a subdivision of $H$ as a subgraph. The branch vertices of the subdivision are its nodes. $H$ is a minor of $G$ , written $H ≼ G$ , if $H$ arises from a subgraph of $G$ by contracting edges (equivalently, via disjoint connected branch sets, as fixed in 40.04.01).

Definition (planar duality). Given a connected plane graph $G$ , its dual $G^{*}$ has one vertex per face of $G$ and one edge per edge $e$ of $G$ , joining the two faces that $e$ borders (a bridge of $G$ borders one face on both sides, producing a loop in $G^{*}$ ). The dual is again a plane graph, drawn with each dual vertex inside its face and each dual edge crossing the corresponding primal edge once. Duality interchanges the cycle and bond (minimal edge cut) structure: a set of edges is a cycle in $G$ iff the corresponding dual edges form a bond in $G^{*}$ ^{[Whitney 1932]}. A graph $G^{*}$ is an abstract dual of $G$ if there is a bijection between their edge sets carrying cycles of $G$ to bonds of $G^{*}$ and conversely.

Counterexamples to common slips

Planar is an abstract property; plane is a drawing. A planar graph has many inequivalent plane embeddings in general; the faces and the dual depend on the embedding, not on the graph alone. Only for $3$ -connected graphs is the embedding essentially unique (Whitney).
The dual depends on the embedding. Two plane embeddings of the same planar graph can have non-isomorphic duals. The $2$ -connected hypothesis fails to pin the dual down; $3$ -connectivity does, which is why duality is cleanest for polytope skeletons.
The edge bound needs at least three vertices. The inequality $e \leq 3 n - 6$ holds for $n \geq 3$ . For $n = 1, 2$ it fails numerically, since a single edge already gives $e = 1 > 3 \cdot 2 - 6 = 0$ ; the bound is a face-counting statement that needs a cycle to bound a face.
Minor and topological minor diverge above degree three. Every topological minor is a minor, but not conversely; $K_{5}$ as a minor of a graph need not appear as a subdivision. For the planarity obstructions the two notions happen to give the same answer (Kuratowski versus Wagner), a coincidence special to $K_{5}$ and $K_{3, 3}$ .

Key theorem with proof Intermediate+

Theorem (Euler's formula and its corollaries). Let $G$ be a connected plane graph with $n$ vertices, $e$ edges, and $f$ faces.

(a) Euler's formula. $n - e + f = 2$ .

(b) Edge bound. If $n \geq 3$ , then $e \leq 3 n - 6$ ; if in addition $G$ is triangle-free, then $e \leq 2 n - 4$ .

(c) Non-planarity. $K_{5}$ and $K_{3, 3}$ are not planar.

(d) Light vertex. Every planar graph has a vertex of degree at most $5$ .

(See ^{[Diestel 2017 §4.2]}, ^{[West 2001 §6.1]}.)

Proof. Part (a). Induct on $e$ . If $e = n - 1$ then $G$ is a connected graph with $n - 1$ edges, hence a tree (by the tree characterisation of 40.04.01); a tree has no cycle, so its drawing bounds no region and has the single outer face, giving $f = 1$ and $n - (n - 1) + 1 = 2$ . If $e \geq n$ , then $G$ contains a cycle; pick an edge $ϵ$ lying on a cycle. By the Jordan curve theorem $ϵ$ borders two distinct faces, so deleting $ϵ$ merges those two faces into one, reducing both $e$ and $f$ by exactly one while keeping the graph connected. The smaller graph satisfies $n - (e - 1) + (f - 1) = 2$ by induction, and adding the two cancelling units restores $n - e + f = 2$ .

Part (b). Assume $n \geq 3$ and, first, that $G$ has a cycle (otherwise $e \leq n - 1 \leq 3 n - 6$ at once). Each face is bounded by at least three edges in a simple plane graph with a cycle, and each edge lies on the boundary of at most two faces. Summing edge-incidences face by face, $3 f \leq 2 e$ , so $f \leq \frac{2}{3} e$ . Substituting into Euler's formula, $2 = n - e + f \leq n - e + \frac{2}{3} e = n - \frac{1}{3} e$ , which rearranges to $e \leq 3 n - 6$ . If $G$ is triangle-free, every face is bounded by at least four edges, so $4 f \leq 2 e$ , giving $f \leq \frac{1}{2} e$ and $2 \leq n - \frac{1}{2} e$ , i.e. $e \leq 2 n - 4$ .

Part (c). $K_{5}$ has $n = 5$ and $e = 10$ , but $3 n - 6 = 9 < 10$ , so $K_{5}$ violates the edge bound and cannot be planar. $K_{3, 3}$ has $n = 6$ , $e = 9$ , and is triangle-free (bipartite graphs have no odd cycle, by 40.04.01); the triangle-free bound gives $2 n - 4 = 8 < 9$ , so $K_{3, 3}$ cannot be planar either.

Part (d). If every vertex had degree at least $6$ , the handshake lemma of 40.04.01 would give $2 e = \sum_{v} d (v) \geq 6 n$ , so $e \geq 3 n$ , contradicting $e \leq 3 n - 6$ for $n \geq 3$ (and the claim is immediate for $n \leq 2$ ). Hence some vertex has degree at most $5$ . $□$

Bridge. Euler's formula builds toward the entire structure theory of planar graphs and appears again in every later face-counting, colouring, and duality argument, because it converts the global drawing into a single linear identity among local counts. The foundational reason the edge bound, the two non-planarity facts, and the light-vertex statement sit together is that each is the same face-counting inequality read against the handshake lemma: the bound $3 f \leq 2 e$ is the planar dual of the degree sum, so this is exactly the principle that a planar graph is sparse, with a linear rather than quadratic number of edges. The light-vertex corollary is dual to the edge bound — average sparsity forces a low-degree vertex just as it did for the averaging lemma of 40.04.01 — and putting these together gives the inductive engine behind the five-colour theorem, where a degree- $\leq 5$ vertex is removed, the rest is coloured, and the vertex is reinserted. The central insight is that planarity is a sparsity constraint with a topological origin, and the bridge is the dual graph, which turns these face counts into the cycle-bond duality that the master tier develops into Whitney's planarity criterion.

Exercises Intermediate+

Exercise 4 (medium, short-answer).

Show that $K_{3, 3}$ is not planar by a direct face-counting argument, without quoting the triangle-free bound as a black box.

Hint

$K_{3, 3}$ is bipartite, so it has no odd cycle; the shortest cycle has length four. Bound the faces accordingly.

Answer

Suppose $K_{3, 3}$ were planar with a plane embedding having $f$ faces. It is connected with $n = 6$ and $e = 9$ , so Euler's formula gives $f = 2 - 6 + 9 = 5$ . Being bipartite, $K_{3, 3}$ has no cycle of odd length (by 40.04.01), so its girth is $4$ ; every face boundary is a closed walk of length at least $4$ . Counting edge-face incidences, $\sum_{faces} (boundary length) = 2 e = 18$ , since each edge borders two faces. With $5$ faces each of boundary length at least $4$ , the left side is at least $4 \cdot 5 = 20 > 18$ , a contradiction. Hence $K_{3, 3}$ is not planar. Rubric: full credit for the girth- $4$ observation, the incidence count $2 e$ , and the contradiction $20 > 18$ .

Exercise 5 (medium, short-answer).

Prove that every simple planar graph is $6$ -degenerate: every subgraph has a vertex of degree at most $5$ . Deduce that planar graphs are $6$ -colourable.

Hint

A subgraph of a planar graph is planar, so the light-vertex corollary applies to it; then colour greedily by repeatedly removing a low-degree vertex.

Answer

Every subgraph $H$ of a planar graph is itself planar, so by the light-vertex corollary $H$ has a vertex of degree at most $5$ ; this is the definition of $6$ -degeneracy. For the colouring, order the vertices $v_{1}, \dots, v_{n}$ by repeatedly removing a vertex of degree at most $5$ from the current graph and prepending it, so each $v_{i}$ has at most $5$ neighbours among $v_{1}, \dots, v_{i - 1}$ . Colour in the order $v_{1}, \dots, v_{n}$ with colours ${1, \dots, 6}$ , giving each $v_{i}$ a colour avoided by its at most $5$ earlier neighbours; such a colour exists since six colours are available. The result is a proper $6$ -colouring. Rubric: full credit for hereditary planarity, the degeneracy ordering, and the greedy colouring.

Exercise 7 (hard, short-answer).

Prove that a maximal planar graph on $n \geq 3$ vertices (one to which no edge can be added while preserving planarity) is a triangulation, and has exactly $3 n - 6$ edges.

Hint

If some face had a boundary longer than a triangle, find two non-adjacent boundary vertices and add a chord inside the face.

Answer

Fix a plane embedding of a maximal planar graph $G$ with $n \geq 3$ . Suppose some face $ϕ$ had a boundary that is not a triangle. The boundary, being a closed walk in a maximal hence $2$ -connected graph, is a cycle of length at least $4$ (it cannot be a single edge traversed twice without a cut vertex). Two vertices $u, w$ on this cycle are non-adjacent on the boundary and not already joined by an edge inside $ϕ$ ; the arc of $ϕ$ lets one draw a new edge $u w$ inside $ϕ$ without crossing, since $ϕ$ is an open region bounded by the cycle. If $u, w$ were already adjacent elsewhere, the edge drawn inside $ϕ$ is still a new parallel-free edge in the simple graph only if they were non-adjacent; choosing two boundary vertices at cyclic distance $2$ guarantees non-adjacency in a triangle-free-bounded face. Adding it keeps the graph planar, contradicting maximality. Hence every face is a triangle, so $3 f = 2 e$ ; with Euler's formula $n - e + \frac{2}{3} e = 2$ this gives $e = 3 n - 6$ . Rubric: full credit for the chord-insertion argument forcing triangular faces and the resulting edge count.

Exercise 8 (hard, short-answer).

Prove that any two plane embeddings of a connected planar graph $G$ have the same number of faces, even though the cyclic edge-orderings around vertices may differ.

Hint

The face count is determined by $n$ and $e$ alone, through a formula that does not mention the embedding.

Answer

Let $G$ be connected planar with $n$ vertices and $e$ edges, and let two plane embeddings have $f_{1}$ and $f_{2}$ faces respectively. Euler's formula applies to each embedding because each is a connected plane graph with the same underlying $G$ : $n - e + f_{1} = 2$ and $n - e + f_{2} = 2$ . Subtracting, $f_{1} - f_{2} = 0$ , so $f_{1} = f_{2}$ . The face count is thus an invariant of the abstract graph, fixed by $f = 2 - n + e$ , regardless of which crossing-free drawing realises it; the embeddings may differ in their rotation systems and hence in face boundaries, but never in the total number of faces. Rubric: full credit for applying Euler's formula to both embeddings and subtracting.

Advanced results Master

Theorem (Kuratowski). A graph is planar if and only if it contains no subdivision of $K_{5}$ and no subdivision of $K_{3, 3}$ — equivalently, neither $K_{5}$ nor $K_{3, 3}$ as a topological minor. (Kuratowski ^{[Kuratowski 1930]}; Diestel ^{[Diestel 2017 §4.5]}.) Necessity is the easy direction: planarity is preserved under taking subgraphs and under suppressing degree-two vertices, so a planar graph cannot contain a subdivision of a non-planar graph, and $K_{5}, K_{3, 3}$ are non-planar by Euler's formula. Sufficiency is the substance and is proved by reduction to the $3$ -connected case: one shows that a minor-minimal non-planar graph is $3$ -connected, and that every $3$ -connected graph with no $K_{5}$ or $K_{3, 3}$ minor is planar, using that a $3$ -connected graph on at least five vertices has an edge whose contraction is again $3$ -connected (Tutte's wheel theorem provides the inductive ladder).

Theorem (Wagner). A graph is planar if and only if it has neither $K_{5}$ nor $K_{3, 3}$ as a minor. (Wagner ^{[Wagner 1937]}.) For the obstruction graphs the minor and topological-minor versions coincide: a $K_{3, 3}$ minor always yields a $K_{3, 3}$ subdivision because $K_{3, 3}$ has maximum degree $3$ , and a $K_{5}$ minor that is not a $K_{5}$ subdivision can be re-routed into a $K_{3, 3}$ subdivision, so forbidding the two minors is equivalent to forbidding the two subdivisions. Wagner additionally analysed the graphs with no $K_{5}$ minor that are not planar, showing they are built from planar pieces and copies of the Wagner graph $V_{8}$ by clique-sums over triangles — the Wagner decomposition that anticipates the structure theorems of graph-minor theory.

Proof sketch (Kuratowski via $3$ -connected reduction). Let $G$ be edge-minimal non-planar, so $G$ has no $K_{5}$ or $K_{3, 3}$ topological minor but is non-planar while every proper subgraph and every minor is planar. First, $G$ is $2$ -connected, for a cut vertex would split $G$ into planar blocks that re-glue planarly at the cut vertex. Next, $G$ is $3$ -connected: a $2$ -separation ${u, v}$ splits $G$ into parts $G_{1}, G_{2}$ ; minimality makes $G_{i} + uv$ planar, and one embeds them sharing the edge $uv$ on a common face, re-gluing to a plane embedding of $G$ unless a $K_{5}$ or $K_{3, 3}$ subdivision is exposed. For $3$ -connected $G$ , take an edge $x y$ whose contraction $G / x y$ stays $3$ -connected (such an edge exists for $∣ G ∣ \geq 5$ ). By minimality $G / x y$ is planar; in its essentially unique embedding (Whitney), the neighbours of the contracted vertex lie on a common face, and re-expanding the contracted vertex either yields a plane embedding of $G$ or forces a $K_{5}$ or $K_{3, 3}$ subdivision in $G$ , against the hypothesis. The contradiction shows no minimal non-planar graph avoids both obstructions, proving sufficiency ^{[Diestel 2017 §4.5]}.

Theorem (Whitney's planarity criterion). A graph $G$ is planar if and only if it has an abstract dual. (Whitney ^{[Whitney 1932]}.) The geometric dual of a plane embedding is an abstract dual, giving necessity. Conversely, the existence of a combinatorial dual — a graph $G^{*}$ with a cycle-bond-interchanging edge bijection — is an algebraic condition equivalent to the cycle matroid of $G$ being co-graphic, which MacLane's parallel criterion phrases as the cycle space of $G$ having a basis in which every edge lies in at most two basis cycles. Both are purely combinatorial certificates of planarity, independent of any drawing.

Theorem (Whitney unique embedding; Steinitz). Every $3$ -connected planar graph has an essentially unique embedding in the sphere: its face boundaries are determined up to the choice of outer face and reflection. (Whitney ^{[Whitney 1932]}; Mohar-Thomassen ^{[Mohar-Thomassen 2001 Ch. 2]}.) Consequently the dual of a $3$ -connected planar graph is a graph invariant, not merely an embedding invariant. Steinitz's theorem identifies these graphs concretely: a graph is the vertex-edge skeleton ( $1$ -skeleton) of a $3$ -dimensional convex polytope if and only if it is $3$ -connected and planar ^{[Steinitz 1922]}. Under this correspondence planar duality becomes polytope (combinatorial) polarity, the cube dualising to the octahedron and the dodecahedron to the icosahedron.

Synthesis. These results are one phenomenon — the sparsity and topological rigidity of planar graphs — seen at increasing depth, and putting these together the whole chapter becomes the study of how a global drawing constraint reduces to a finite local certificate. The foundational reason Euler's formula, the two forbidden graphs, and the unique embedding cohere is that planarity is simultaneously a counting constraint ( $e \leq 3 n - 6$ ), a forbidden-pattern constraint (no $K_{5}$ or $K_{3, 3}$ ), and a matroid-duality constraint (an abstract dual exists), and the central insight is that all three describe the same minor-closed class. Kuratowski's topological-minor form is dual to Wagner's minor form, the two coinciding precisely because the obstructions have low degree; this is exactly the principle that for the planar obstructions the subdivision and contraction orderings agree, a coincidence that fails for general $H$ . The bridge onward is the graph-minor theorem: planarity is the first and cleanest instance of a minor-closed property with a finite forbidden-minor set, and Wagner's clique-sum decomposition of $K_{5}$ -minor-free graphs generalises into the full structure theory, where every proper minor-closed class has a bounded-genus, bounded-treewidth, clique-sum description. The unique-embedding and Steinitz theorems supply the other face of the same rigidity: a $3$ -connected planar graph is so constrained that it determines a convex polytope, so the combinatorics of planarity and the geometry of polyhedra are two readings of one $3$ -connected skeleton.

Full proof set Master

Proposition 1 (Euler's formula). A connected plane graph with $n$ vertices, $e$ edges, $f$ faces satisfies $n - e + f = 2$ .

Proof. Induct on $e$ . The base case $e = n - 1$ : a connected graph with $n - 1$ edges is a tree, its drawing encloses no region, so $f = 1$ and $n - (n - 1) + 1 = 2$ . Inductive step $e \geq n$ : the graph has a cycle, so some edge $ϵ$ lies on a cycle $C$ . By the Jordan curve theorem $C$ separates the plane, so $ϵ$ borders two distinct faces. Removing $ϵ$ keeps the graph connected (the rest of $C$ still joins $ϵ$ 's endpoints), merges its two bordering faces into one, and so decreases $e$ by $1$ and $f$ by $1$ . The resulting connected plane graph satisfies $n - (e - 1) + (f - 1) = 2$ by induction, hence $n - e + f = 2$ . $□$

Proposition 2 (edge bounds). For a simple connected plane graph with $n \geq 3$ : $e \leq 3 n - 6$ ; if triangle-free, $e \leq 2 n - 4$ .

Proof. If $G$ is acyclic then $e \leq n - 1 \leq 3 n - 6$ . Otherwise each face boundary contains at least three edges, and since each edge borders at most two faces, summing boundary lengths gives $3 f \leq \sum_{faces} ℓ (face) = 2 e$ , so $f \leq \frac{2}{3} e$ . Euler's formula yields $2 = n - e + f \leq n - e + \frac{2}{3} e = n - \frac{1}{3} e$ , i.e. $e \leq 3 (n - 2) = 3 n - 6$ . If $G$ is triangle-free its girth is at least $4$ , so each face boundary has length at least $4$ , giving $4 f \leq 2 e$ , $f \leq \frac{1}{2} e$ , and $2 \leq n - \frac{1}{2} e$ , i.e. $e \leq 2 n - 4$ . $□$

Proposition 3 (non-planarity of $K_{5}$ and $K_{3, 3}$ ). Neither $K_{5}$ nor $K_{3, 3}$ is planar.

Proof. $K_{5}$ : $n = 5$ , $e = 10$ ; the bound $e \leq 3 n - 6 = 9$ is violated, so no plane embedding exists. $K_{3, 3}$ : $n = 6$ , $e = 9$ , bipartite hence triangle-free; the bound $e \leq 2 n - 4 = 8$ is violated, so it is not planar. $□$

Proposition 4 (light vertex and $6$ -degeneracy). Every simple planar graph has a vertex of degree at most $5$ , and is $6$ -degenerate.

Proof. For $n \leq 6$ some vertex has degree at most $n - 1 \leq 5$ . For $n \geq 3$ , if every degree were at least $6$ then $2 e = \sum_{v} d (v) \geq 6 n$ , so $e \geq 3 n > 3 n - 6$ , contradicting Proposition 2; hence the minimum degree is at most $5$ . Every subgraph of a planar graph is planar, so the same bound applies to each subgraph, which is the definition of $6$ -degeneracy. $□$

Proposition 5 (Euler-formula duality of cycles and bonds). For a connected plane graph $G$ with dual $G^{} $, a se t o f e d g es f or m s a cy c l e in$ G $i f an d o n l y i f t h ecor r es p o n d in g d u a l e d g es f or maminima l e d g ec u t (b o n d) in$ G^{}$.

Proof. A cycle $C$ in $G$ is a simple closed curve in the plane; by the Jordan curve theorem it separates the faces of $G$ into those inside $C$ and those outside. The dual vertices split accordingly into an inside class $S^{*}$ and an outside class, and a dual edge crosses $C$ iff its primal edge lies on $C$ , so the dual edges of $C$ are exactly the edges of $G^{*}$ between $S^{*}$ and its complement — a cut. Minimality: removing any proper subset of $C$ leaves $C$ connected as a curve, so the corresponding dual-edge subset does not disconnect $S^{*}$ from its complement, hence the cut is a bond. Conversely a bond of $G^{*}$ separates $G^{*}$ into two connected parts; the primal edges crossing it bound the union of faces on one side, whose boundary is a single closed curve, i.e. a cycle of $G$ . Thus cycles and bonds correspond under duality. $□$

Proposition 6 (maximal planar graphs are triangulations with $3 n - 6$ edges). A maximal planar graph on $n \geq 3$ vertices is a triangulation and has exactly $3 n - 6$ edges.

Proof. Fix a plane embedding. If some face had boundary length at least $4$ , two of its boundary vertices are non-adjacent across the face interior and can be joined by an arc drawn inside the face without crossing any edge, since the face is an open region; the added edge preserves simplicity and planarity, contradicting maximality. (Non-adjacency of a suitable pair holds because a face of length $\geq 4$ in a simple plane graph has two boundary vertices at cyclic distance two that are not joined inside the face.) Hence every face is a triangle, so $3 f = 2 e$ . Euler's formula gives $n - e + \frac{2}{3} e = 2$ , i.e. $\frac{1}{3} e = n - 2$ , so $e = 3 n - 6$ and $f = 2 n - 4$ . $□$

Connections Master

Graphs, basic invariants, and the foundational lemmas 40.04.01. Planarity is the first place the minor and topological-minor orders introduced there do real structural work: Kuratowski's theorem and Wagner's theorem are the topological-minor and minor characterisations of a single class, and the proofs rest on the handshake lemma (the light-vertex corollary), the tree characterisation (the base case of Euler's formula), and the no-odd-cycle bipartiteness criterion (the triangle-free edge bound applied to $K_{3, 3}$ ). This unit specialises the abstract containment relations defined upstream into the concrete obstruction theory that makes planarity decidable.
Map colouring: the four- and five-colour theorems 40.04.08. The edge bound and the light-vertex corollary proved here are exactly the inputs to the five-colour theorem: a planar graph has a vertex of degree at most $5$ , which the discharging and Kempe-chain arguments of that unit remove, colour, and reinsert. The four-colour theorem sharpens this further, and the entire colouring chapter takes the sparsity $e \leq 3 n - 6$ as its standing hypothesis, so the present unit owns the structural facts that the colouring unit consumes.
The graph-minor theorem and forbidden-minor characterisations 40.04.10. Wagner's theorem is the prototype of a forbidden-minor characterisation, and the clique-sum decomposition of $K_{5}$ -minor-free graphs sketched in the Advanced results is the first instance of the structure theorems that the graph-minors unit develops. Planarity, as a minor-closed property with the finite obstruction set ${K_{5}, K_{3, 3}}$ , is the cleanest case of the Robertson-Seymour theorem that every minor-closed class has a finite forbidden-minor set, so this unit supplies the motivating example for that one.
Vertex connectivity and Menger's theorem 40.04.04. The reduction to the $3$ -connected case is the engine of Kuratowski's proof, and the unique-embedding theorem of Whitney is a $3$ -connectivity phenomenon. The connectivity unit owns the $k$ -connected structure theory and the contraction-preserving-connectivity lemmas (Tutte's wheel theorem) that the planarity proof invokes, so this unit is downstream of the connectivity machinery developed there.

Historical & philosophical context Master

Euler's formula originates in Leonhard Euler's 1750-1758 correspondence and the paper Elementa doctrinae solidorum (Novi Commentarii Academiae Scientiarum Petropolitanae), where Euler observed for convex polyhedra that vertices minus edges plus faces equals two ^{[Euler 1758]}. The polyhedral statement and the plane-graph statement are the same fact, since projecting a convex polyhedron from an interior point onto a surrounding sphere and then stereographically to the plane turns its skeleton into a plane graph with the polyhedron's faces; this identification is made precise by Steinitz's 1922 theorem ^{[Steinitz 1922]} that the $3$ -connected planar graphs are exactly the polytope skeletons. The forbidden-graph characterisation of planarity was proved by Kazimierz Kuratowski in 1930 in Sur le problème des courbes gauches en topologie (Fundamenta Mathematicae 15) ^{[Kuratowski 1930]}, with independent contemporaneous work by Frink and Smith and by Pontryagin.

Klaus Wagner's 1937 paper Über eine Eigenschaft der ebenen Komplexe (Mathematische Annalen 114) ^{[Wagner 1937]} recast Kuratowski's subdivision condition as a minor condition and analysed the $K_{5}$ -minor-free graphs via clique-sums, the decomposition that Robertson and Seymour would generalise five decades later. Hassler Whitney, in a sequence of papers in 1932-1933 ^{[Whitney 1932]}, established the combinatorial theory of duality, the abstract-dual planarity criterion, and the unique embedding of $3$ -connected planar graphs, founding what became matroid theory in the process. The topological input throughout is the Jordan curve theorem, first stated by Camille Jordan in 1887 and rigorously proved by Oswald Veblen in 1905, whose role in graph theory is confined to the single separation fact that a cycle has an inside and an outside.

Bibliography Master

@book{Diestel2017,
  author    = {Diestel, Reinhard},
  title     = {Graph Theory},
  edition   = {5th},
  series    = {Graduate Texts in Mathematics},
  volume    = {173},
  publisher = {Springer},
  year      = {2017}
}

@book{West2001,
  author    = {West, Douglas B.},
  title     = {Introduction to Graph Theory},
  edition   = {2nd},
  publisher = {Prentice Hall},
  year      = {2001}
}

@book{BondyMurty2008,
  author    = {Bondy, J. A. and Murty, U. S. R.},
  title     = {Graph Theory},
  series    = {Graduate Texts in Mathematics},
  volume    = {244},
  publisher = {Springer},
  year      = {2008}
}

@book{MoharThomassen2001,
  author    = {Mohar, Bojan and Thomassen, Carsten},
  title     = {Graphs on Surfaces},
  publisher = {Johns Hopkins University Press},
  year      = {2001}
}

@article{Kuratowski1930,
  author  = {Kuratowski, Kazimierz},
  title   = {Sur le probl\`eme des courbes gauches en topologie},
  journal = {Fundamenta Mathematicae},
  volume  = {15},
  year    = {1930},
  pages   = {271--283}
}

@article{Wagner1937,
  author  = {Wagner, Klaus},
  title   = {\"Uber eine Eigenschaft der ebenen Komplexe},
  journal = {Mathematische Annalen},
  volume  = {114},
  year    = {1937},
  pages   = {570--590}
}

@article{Whitney1932,
  author  = {Whitney, Hassler},
  title   = {Non-separable and planar graphs},
  journal = {Transactions of the American Mathematical Society},
  volume  = {34},
  year    = {1932},
  pages   = {339--362}
}

@incollection{Steinitz1922,
  author    = {Steinitz, Ernst},
  title     = {Polyeder und Raumeinteilungen},
  booktitle = {Encyklop\"adie der mathematischen Wissenschaften},
  volume    = {IIIAB12},
  year      = {1922},
  pages     = {1--139}
}

@book{Ziegler1995,
  author    = {Ziegler, G\"unter M.},
  title     = {Lectures on Polytopes},
  series    = {Graduate Texts in Mathematics},
  volume    = {152},
  publisher = {Springer},
  year      = {1995}
}

@article{RobertsonSeymour2004,
  author  = {Robertson, Neil and Seymour, Paul D.},
  title   = {Graph Minors. XX. Wagner's conjecture},
  journal = {Journal of Combinatorial Theory, Series B},
  volume  = {92},
  year    = {2004},
  pages   = {325--357}
}

Prerequisites

40.04.01

Tier anchors

beginner: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §4.1-§4.2 (plane graphs, faces, Euler's formula) read for the pictures of drawings without crossings and the faces they cut out; West 2001 *Introduction to Graph Theory* (2nd ed., Prentice Hall) §6.1 for the dots-lines-regions vocabulary and the v − e + f = 2 count on small drawings; 3Blue1Brown's Euler-characteristic essay for the deflated-polyhedron intuition behind faces and the alternating sum
intermediate: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §4.1-§4.2 (topological prerequisites and the Jordan curve theorem's role, plane and planar graphs, Euler's formula and the edge bounds e ≤ 3n − 6 and e ≤ 2n − 4, non-planarity of K_5 and K_{3,3}); West 2001 §6.1; Bondy-Murty 2008 *Graph Theory* (Springer GTM 244) Ch. 10
master: Diestel 2017 *Graph Theory* (5th ed., Springer GTM 173) §4.3-§4.6 (Kuratowski's theorem via 3-connected reduction, the algebraic and abstract-dual criteria of Whitney, the structure of 3-connected planar graphs and Whitney's unique-embedding theorem); Mohar-Thomassen 2001 *Graphs on Surfaces* (Johns Hopkins) Ch. 2-3; Ziegler 1995 *Lectures on Polytopes* (Springer GTM 152) Ch. 4 (Steinitz's theorem); the original sources Euler 1758, Kuratowski 1930, Wagner 1937, Whitney 1932-1933, Steinitz 1922

References

Diestel 2017 — Graph Theory (5th edition) · Springer Graduate Texts in Mathematics 173, 2017, Ch. 4 (§4.1 topological prerequisites and the Jordan curve theorem; §4.2 plane graphs, faces, Euler's formula and its corollaries; §4.3 maximal plane graphs; §4.4 the Jordan-Schoenflies theorem and bridges; §4.5 planar graphs and Kuratowski's theorem; §4.6 algebraic planarity and Whitney's criterion)
West 2001 — Introduction to Graph Theory (2nd edition) · Prentice Hall, 2001, §6.1-§6.2 (planar drawings, Euler's formula, Kuratowski's and Wagner's theorems, planar duality)
Bondy, Murty 2008 — Graph Theory · Springer Graduate Texts in Mathematics 244, 2008, Ch. 10 (planar graphs, Euler's formula, duality, Kuratowski's theorem)
Mohar, Thomassen 2001 — Graphs on Surfaces · Johns Hopkins University Press, 2001, Ch. 2-3 (planarity, the Jordan curve theorem, Kuratowski's theorem, 2- and 3-connected planar graphs and unique embeddings)
Kuratowski 1930 — Sur le problème des courbes gauches en topologie · Fundamenta Mathematicae 15 (1930) 271-283; the forbidden-subdivision characterisation of planarity
Wagner 1937 — Über eine Eigenschaft der ebenen Komplexe · Mathematische Annalen 114 (1937) 570-590; the forbidden-minor characterisation and the K_5 reduction
Whitney 1932 — Non-separable and planar graphs · Transactions of the American Mathematical Society 34 (1932) 339-362; combinatorial duality, abstract duals, and the unique embedding of 3-connected planar graphs
Steinitz 1922 — Polyeder und Raumeinteilungen · Encyklopädie der mathematischen Wissenschaften IIIAB12 (1922); the characterisation of 3-connected planar graphs as polytope skeletons

Estimated time

beginner: 18m
intermediate: 46m
master: 86m