Graph Theory 101: Why all Non-Planar Graphs Contain K₅ or K₃,₃
An intuitive explanation of Kuratowski’s Theorem and Wagner’s Theorem, with lots of diagrams!
Published in
7 min readApr 11, 2022
A planar graph is one that can be drawn in a plane without any edges crossing. For example, the complete graph K₄ is planar, as shown by the “planar embedding” below.
One application of planar graphs would be designing a rail network without any intersections. Another common one is designing an electrical circuit or computer chip without any crossing wires.
Two non-planar graphs are the complete graph K5 and the complete bipartite graph K3,3:
- K5 is a graph with 5 vertices, with one edge between every pair of vertices.
- K3,3 is a graph with 6 vertices in two sets of 3, with one edge between each pair of vertices from opposite sets.
No matter how you draw K5 and K3,3, it is not possible to do so without two edges crossing. This can be proved by showing they have too many edges to satisfy Euler’s theorem for non-planar graphs:
vertices + faces = edges + 2.
