Chapter 14 · Special Topics
Planarity and Euler's Formula
m <= 3n - 6 and what it buys you, the Kuratowski obstruction, the linear-time tests you can actually run, and why planarity keeps appearing in olympiad graph problems.
#Euler's formula
A connected planar graph drawn without crossings, with n vertices, m edges and f faces (the outer face counted), satisfies
Induction on m. A spanning tree has m = n-1, f = 1: equality. Adding an edge between two existing vertices of a connected drawing splits one face into two, so both m and f increase by 1 and n - m + f is unchanged. (Formally: any connected graph is a tree plus m - n + 1 chords, each chord increasing f by exactly 1 because the unique tree path between its endpoints cuts a face.) ∎
#The two edge bounds
For a simple planar graph with n ≥ 3: m ≤ 3n - 6. If additionally the graph has no triangle (bipartite, e.g.): m ≤ 2n - 4.
Every face has boundary length ≥ 3 (simplicity), so 2m = ∑faces |∂| ≥ 3f, i.e. f ≤ 2m/3. Euler: 2 = n - m + f ≤ n - m + tfrac{2m}{3} = n - tfrac m3, giving m ≤ 3n - 6. With girth ≥ 4 replace 3 by 4: f ≤ m/2 and m ≤ 2n - 4. ∎
#A counterexample detector
"K5 is not planar": m = 10 > 3· 5 - 6 = 9. ✓ "K3,3 is not planar": m = 9 > 2· 6 - 4 = 8 (bipartite ⇒ girth 4). ✓ "the dodecahedral graph is planar and has 20 vertices": then f = 2 - n + m = 12, and all faces are pentagons — 2m = 30 = 5f. ✓ These one-line computations settle a large fraction of olympiad planarity questions, and the same counting with 1 ≤ face size gives every planar-family bound (e.g. "at most 3n-6 pairs of touching regions", "some face has ≤ 6 sides" ⇒ min degree ≤ 5 ⇒ five-colour theorem).
#What planarity buys algorithmically
What planarity costs you algorithmically
- Testing planarity: Hopcroft–Tarjan linear time, but nobody writes it; practical options are (a) Boyer–Myrvold via a library (LEMON/NetworkX/OGDF), (b) Kuratowski-subgraph search on small n, (c) for contest problems, planarity is given by the story (a map, a grid, regions) and you only need Euler's formula or a dual construction;
- The dual graph G^*: a vertex per face, an edge per primal edge. G** = G for 2-connected plane graphs; a face of G is a cycle iff the corresponding G^* edges form a bond; spanning trees of G correspond bijectively to spanning trees of G^* (the complement of a tree's edges is a tree in the dual) — which is the cleanest proof that the number of spanning trees is the same for G and G^* (The Matrix–Tree Theorem);
- Planar separators: a planar graph has a set of O(√n) vertices whose removal splits it into parts of size ≤ 2n/3 (Lipton–Tarjan). This is why planar problems admit O(n3/2) or subexponential divide-and-conquer, and why "small treewidth" (Independent Sets, Cliques, and Treewidth's remark) is the generalisation that makes DP possible;
- Four colour theorem: every planar graph is 4-colourable. Its proof is a computer check of 1936 reducible configurations; the algorithmic content is that greedy/DP colouring works because of the "min degree ≤ 5" structure (five-colouring is elementary and linear, Graph Colouring), and that 4-colouring a given planar graph is O(n2) (Robertson–Sanders–Seymour–Thomas), not something you implement.
#Three statements people get wrong
- m ≤ 3n-6 is necessary, not sufficient: the Petersen graph has n=10, m=15 ≤ 24 and is non-planar. Only K5 and K3,3 subdivisions/minors are the real obstruction (Kuratowski: non-planar ⟺ contains a subdivision of K5 or K3,3; Wagner: ⟺ has one as a minor, which is the stronger and cleaner form).
- Planarity depends on the abstract graph, not the drawing: a drawing with crossings proves nothing (a graph can be planar yet look tangled in your sketch). "It has a crossing" ≠ "non-planar"; only the absence of any crossing-free drawing does.
- Euler's formula needs connected: for c components, n - m + f = 1 + c. Forgetting c is the standard off-by-1 in "count the regions" problems (and the region count includes the outer one).
#A contest-shaped application
"Each pair of n cities is joined by a road or a railway; no three cities are pairwise joined by the same type. Prove that one type appears at most 2n-4 times." Model each type as a graph; the condition says both are triangle-free. If the statement also gives a crossing-free drawing of each (that is the extra hypothesis in the real problem — otherwise it is false for large n, since a triangle-free graph can have up to n2/4 edges by Turán), then m ≤ 2n-4 applies to each by the girth-4 corollary. The lesson is the order of the argument: name the graph, prove triangle-freeness, prove planarity, only then count.