4.5Planarity
The idea
A graph is planar if it can be drawn on a plane with no edges crossing. Euler's formula v − e + f = 2 relates vertices, edges and faces of a connected planar graph.
Think of it like this: A circuit board with no wire crossings: planar graphs are exactly the networks you can lay out flat.
Why it exists
Counting faces, and ruling out planarity with an edge bound, appear often. K₅ and K₃,₃ are the standard non-planar examples.
How it works
- v − e + f = 2 for connected planar graphs.
- Simple planar graph (v ≥ 3): e ≤ 3v − 6; triangle-free: e ≤ 2v − 4.
- Every planar graph has a vertex of degree ≤ 5.
- Kuratowski: planar iff no subdivision of K₅ or K₃,₃. Failing the edge bound proves non-planar; passing it proves nothing.
Worked example: Is K₃,₃ planar?
v = 6, e = 9. It is bipartite, so planarity would need e ≤ 2·6 − 4 = 8. 9 > 8, so not planar.
Now play with it
- →Load K₅ and see e = 10 above the bound 9.
- →Load the wheel W₅ and read faces = e − v + 2.
Passing the bounds does not prove planarity. K₅ and K₃,₃ are the two minimal non-planar graphs (Kuratowski): a graph is planar iff it has no subdivision of either.
Check yourself
A connected planar graph has 8 vertices and 12 edges. How many faces (including the outer one)?
Exam notes (the dense version)
A planar graph can be drawn with no crossings. Euler's formula: v − e + f = 2 for a connected planar graph. For simple planar graphs with v ≥ 3: e ≤ 3v − 6; if also triangle-free (e.g. bipartite): e ≤ 2v − 4. Every planar graph has a vertex of degree ≤ 5. Kuratowski: planar iff no subdivision of K₅ or K₃,₃. K₄ is planar; K₅ and K₃,₃ are not. The sum of face degrees = 2e.
Previous year questions: Graph Theory (24)
PYQs are grouped by topic, so this is the full set for Graph Theory; try the ones that match this subtopic. Open all 24 on the topic page.