1
Planar means a crossing-free drawing exists
Not that a particular drawing has no crossings. K₄ drawn with a crossing is still planar.
Lesson · Graphs and Trees · Colouring and planarity
Planar Graphs and Euler's Formula
A planar graph can be drawn with no edges crossing. Euler's formula V − E + F = 2 bounds how many edges such a graph can have, and Kuratowski's theorem says exactly which graphs fail.
V − E + F = 2 Euler's formula, connected planar
E ≤ 3V − 6 for V ≥ 3
E ≤ 2V − 4 if additionally triangle-free
K₅ and K_{3,3} are the obstructions (Kuratowski)
One formula, several consequences
Core ideas
What this lesson establishes
Planarity is a property of the graph, not of a drawing, and Euler's formula is what makes it computable.
2
Euler's formula counts faces
V − E + F = 2 for any connected planar drawing, including the unbounded outer face.
3
Two graphs are the only obstructions
Kuratowski: a graph is planar exactly when it contains no subdivision of K₅ or K_{3,3}.
The material
Planarity
Euler's formula, the edge bounds it gives, and the two forbidden graphs.
Definition · Planar graph, face
A graph is planar if it can be drawn in the plane with no two edges crossing. Such a drawing divides the plane into faces, including one unbounded outer face.
Theorem · Euler's formula
For a connected planar graph drawn without crossings, V − E + F = 2, where F counts the faces including the outer one.
By induction on the number of edges. A connected graph with no cycle is a tree: E = V − 1 and F = 1, so V − (V−1) + 1 = 2.
If the graph has a cycle, remove one of its edges. The graph stays connected, and the two faces on either side of that edge merge into one, so E and F each drop by 1 and V − E + F is unchanged. Repeating reaches a tree.
□
Example · A cube
The graph of a cube has V = 8, E = 12, F = 6, and 8 − 12 + 6 = 2. The same holds for every convex polyhedron — which is where Euler first stated it, in 1758.
Theorem · The edge bound
A simple connected planar graph with V ≥ 3 has E ≤ 3V − 6. If it is also triangle-free, E ≤ 2V − 4.
Every face is bounded by at least 3 edges, and every edge borders at most 2 faces. Counting edge–face incidences two ways gives 3F ≤ 2E.
Substituting F = 2 − V + E into 3F ≤ 2E gives 3(2 − V + E) ≤ 2E, hence E ≤ 3V − 6.
If there are no triangles, every face has at least 4 edges, so 4F ≤ 2E and the same substitution gives E ≤ 2V − 4.
□
The double count is the handshake theorem's argument applied to faces instead of vertices, which is worth noticing: the same technique keeps returning.
Theorem · K₅ and K_{3,3} are not planar
Neither can be drawn without crossings.
K₅ has V = 5 and E = 10. The bound gives E ≤ 3(5) − 6 = 9 < 10, so it is not planar.
K_{3,3} has V = 6 and E = 9, and satisfies E ≤ 3V − 6 = 12. But it is bipartite hence triangle-free, so the sharper bound applies: E ≤ 2(6) − 4 = 8 < 9. Not planar.
□
Two graphs, two bounds, and the second needed the triangle-free version — which is why both were derived. K_{3,3} is the classic "three utilities to three houses" puzzle, and it has no solution.
Theorem · Kuratowski's theorem
A graph is planar if and only if it contains no subgraph that is a subdivision of K₅ or of K_{3,3}. A subdivision replaces edges by paths through new degree-2 vertices.
This is a complete characterisation by two forbidden structures, which is remarkable: infinitely many graphs are non-planar and all of them fail for one of two reasons. Planarity can also be tested in linear time, though the algorithms are intricate.
Theorem · Consequences for colouring
Every planar graph has a vertex of degree at most 5, since otherwise 2E = Σ deg(v) ≥ 6V, contradicting E ≤ 3V − 6. That fact is the base of the induction proving the five-colour theorem, and the starting point of the four-colour proof.
So this course ends where it began: with the handshake theorem. Counting degrees gave Euler's criterion in “Euler and Hamilton Paths”, the tree edge count in “Trees”, and now the degree bound that makes planar graphs colourable.
Interactive
Graph workbench
Your graph, the course's algorithms
Method
Testing planarity
Count first; the bound settles many cases.
1
Check E ≤ 3V − 6
If it fails, the graph is not planar and you are finished. Cheap and conclusive when it fires.
2
If triangle-free, check E ≤ 2V − 4
The sharper bound, and the one that rules out K_{3,3}.
3
Look for K₅ or K_{3,3} subdivisions
By Kuratowski these are the only obstructions. Finding one is a complete proof of non-planarity.
4
Otherwise try to draw it
The bounds are necessary and not sufficient, so passing them does not establish planarity. A crossing-free drawing does.
Planarity
Score 0 / 0Choose the answer you can justify.
Three graphs tested
The bound, the sharper bound, and a case it cannot settle.
K₅ V=5 E=10 3V−6 = 9 < 10 NOT PLANAR
K_{3,3} V=6 E=9 3V−6 = 12 ≥ 9 inconclusive
bipartite ⟹ triangle-free
2V−4 = 8 < 9 NOT PLANAR
Petersen V=10 E=15 3V−6 = 24 ≥ 15 inconclusive
triangle-free: 2V−4 = 16 ≥ 15 still inconclusive
It contains a K_{3,3} subdivision ⟹ NOT PLANAR
(Kuratowski)
The Petersen graph passes both counting bounds and is still not planar, which shows the bounds are necessary and not sufficient. Only Kuratowski's characterisation settles it, and finding the subdivision is the work.
Common mistakes
1
Concluding planarity from the edge boundIt is necessary and not sufficient. The Petersen graph satisfies both bounds and is not planar.
2
Forgetting the outer faceEuler's formula counts it. Omitting it gives V − E + F = 1 and every subsequent bound is wrong.
3
Applying the triangle-free bound to a graph with trianglesE ≤ 2V − 4 requires girth at least 4. Using it otherwise rules out planar graphs incorrectly.
Check your understanding
✓
Finish when you can rule out planarity by counting.
Take K_{4,4}: V = 8, E = 16, triangle-free. 2V − 4 = 12 < 16, so it is not planar — settled by arithmetic, with no drawing attempted.
Note: Euler's formula generalises to surfaces: on a torus V − E + F = 0, and graphs that cannot be drawn in the plane can often be drawn there. K₅ and K_{3,3} both embed in a torus, and the genus of a graph measures how many handles it needs.