Maths WorkshopMaths problems with full solutions
Exercise 1688Combinatorics › Graph theoryL1Added 3 Nov 2026

$K_{3,3}$ is not planar

#bipartite#planarity#K33

Statement

Show that K3,3K_{3,3} is not planar.

Hint

For bipartite planar graphs, 4f≤2e4f\le 2e (faces have at least 44 edges). Apply Euler's formula.

Show solutionHide solution

Solution

Parameters. K3,3K_{3,3}: v=6v=6, e=9e=9, bipartite.

Euler. If planar, f=2−6+9=5f=2-6+9=5.

Face bound. Since K3,3K_{3,3} is bipartite, every cycle has length ≥4\ge4, so every face has ≥4\ge4 edges. Thus 4f≤2e4f\le2e, i.e. 20≤1820\le18, contradiction.

Conclusion. K3,3K_{3,3} is not planar.