A circuit board cannot let wires cross, and a map's borders never cross. Graphs that can be drawn without crossing edges obey a remarkable formula, proved by building up from a spanning tree one edge at a time.
Key idea
A graph is planar if it can be drawn in the plane with no edges crossing. Such a drawing splits the plane into faces, including the unbounded outside face. Euler's formula: for a connected planar drawing, $$v - e + f = 2.$$ Consequences: a simple planar graph with $v \ge 3$ vertices has $e \le 3v - 6$, and if it has no triangles, $e \le 2v - 4$. So $K_{5}$ and $K_{3,3}$ are not planar.
Why it works
Start with a spanning tree of the drawing: $v$ vertices, $v - 1$ edges, and one face (a tree encloses no region), so $v - e + f = v - (v - 1) + 1 = 2$. Now add the remaining edges one at a time. Each new edge runs through some face and splits it in two, so $e$ and $f$ both go up by $1$, and $v - e + f$ stays $2$. For the bound: every face is bordered by at least $3$ edges and every edge borders at most $2$ faces, so $3f \le 2e$; substituting $f = 2 - v + e$ gives $e \le 3v - 6$.
Worked examples
Worked example: The cube
The cube graph is planar (draw a small square inside a large one and join matching corners). Check Euler's formula.
- $v = 8$ and $e = 12$.
- The drawing has $5$ bounded faces (the small square and four side regions) plus the outside: $f = 6$, one per face of the cube.
- $8 - 12 + 6 = 2$.
Answer: $8 - 12 + 6 = 2$
Worked example: $K_{5}$ is not planar
Use the edge bound to show that $K_{5}$ is not planar.
- $K_{5}$ has $v = 5$ and $e = \binom{5}{2} = 10$.
- A simple planar graph with $5$ vertices has at most $3 \cdot 5 - 6 = 9$ edges.
- $10 > 9$, so $K_{5}$ cannot be planar.
Answer: $e = 10 > 9$
Worked example: $K_{3,3}$ is not planar
$K_{3,3}$ has $9$ edges and $6$ vertices, and $9 \le 3 \cdot 6 - 6 = 12$. Why is it still not planar?
- The bound $e \le 3v - 6$ passes, so it decides nothing.
- $K_{3,3}$ is bipartite, so it has no triangles; every face would need at least $4$ edges, giving $e \le 2v - 4 = 8$.
- $9 > 8$, so it is not planar.
Answer: The triangle-free bound $e \le 8$ fails.
Common mistake
Forgetting the outside face, or using the bound to prove planarity. Counting only the enclosed regions of the cube drawing gives $f = 5$ and $8 - 12 + 5 = 1$. And "$e \le 3v - 6$, so it is planar" is wrong: $K_{3,3}$ passes that test. Check: always count the unbounded face; the edge bounds can only show a graph is not planar.