---
title: "Planarity and Euler's Formula"
summary: 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.
difficulty: hard
tags: [planar, counting, extremal]
prereq: [foundations/types, proofs/double-count]
see: [special/coloring, proofs/double-count]
---


## Euler's formula

:::theorem title="Euler's formula"
A connected planar graph drawn without crossings, with $n$ vertices, $m$ edges and $f$ faces (the outer face counted), satisfies
$$n - m + f = 2 .$$
:::

:::proof
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

:::corollary title="The two inequalities"
For a simple planar graph with $n \ge 3$: $m \le 3n - 6$. If additionally the graph has no triangle (bipartite, e.g.): $m \le 2n - 4$.
:::

:::proof
Every face has boundary length $\ge 3$ (simplicity), so $2m = \sum_{\text{faces}} |\partial| \ge 3f$, i.e. $f \le 2m/3$. Euler: $2 = n - m + f \le n - m + \tfrac{2m}{3} = n - \tfrac m3$, giving $m \le 3n - 6$. With girth $\ge 4$ replace 3 by 4: $f \le m/2$ and $m \le 2n - 4$. ∎
:::

## A counterexample detector

:::note title="Use it as a *counterexample detector*, not an algorithm"
"$K_5$ is not planar": $m = 10 > 3\cdot 5 - 6 = 9$. ✓
"$K_{3,3}$ is not planar": $m = 9 > 2\cdot 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 \le$ face size gives every planar-family bound (e.g. "at most $3n-6$ pairs of touching regions", "some face has $\le 6$ sides" ⇒ min degree ≤ 5 ⇒ five-colour theorem).
:::

## What planarity buys algorithmically

:::props title="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^*$ (@matrices/matrix-tree);
- **Planar separators**: a planar graph has a set of $O(\sqrt n)$ vertices whose removal splits it into parts of size $\le 2n/3$ (Lipton–Tarjan). This is why planar problems admit $O(n^{3/2})$ or subexponential divide-and-conquer, and why "small treewidth" (@special/independent'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, @special/coloring), and that 4-colouring a given planar graph is $O(n^2)$ (Robertson–Sanders–Seymour–Thomas), not something you implement.
:::

## Three statements people get wrong

:::warning title="Three statements people get wrong"
1. $m \le 3n-6$ is **necessary, not sufficient**: the Petersen graph has $n=10, m=15 \le 24$ and is non-planar. Only $K_5$ and $K_{3,3}$ subdivisions/minors are the real obstruction (Kuratowski: non-planar ⟺ contains a subdivision of $K_5$ or $K_{3,3}$; Wagner: ⟺ has one as a **minor**, which is the stronger and cleaner form).
2. 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.
3. 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

:::example title="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 $n^2/4$ edges by Turán), then $m \le 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.
:::

:::problems
- [[CSES 1666]] Building Roads | https://cses.fi/problemset/task/1666 | easy | the word "roads" is not a planarity hypothesis — a calibration exercise in reading
- [[CSES 1752]] Creating Offices | https://cses.fi/problemset/task/1752 | hard | dominating-set style; planar-greedy intuitions fail here, and it is worth seeing why
:::