= Nonplanarity by edge counts
The <complete graph> $K_5$ has $n=5$ and $m=\binom52=10$, exceeding the <planar graph edge bound> $3\cdot5-6=9$. Therefore it is not a <planar graph>. The <complete bipartite graph> $K_{3,3}$ has $n=6$ and $m=3\cdot3=9$. The general bound allows twelve <edges>, but the <bipartite planar graph edge bound> allows only eight, proving nonplanarity.
\Image[/plane-graph-face-counts-and-edge-obstructions.png]
{title=Actual plane-graph face counts compared with impossible face counts for the two complete-graph obstructions}
{id=plane-graph-face-counts-and-edge-obstructions}
These are necessary bounds, not a complete planarity test. For an original counterexample, subdivide every <edge> of $K_{3,3}$ once. The resulting <simple graph> is a <connected graph> with $n=15$, $m=18$, and is <bipartite>: put all original <vertices> in one part and all nine new <vertices> in the other. Both inequalities hold, $18\leq39$ and $18\leq26$. Nevertheless, a crossing-free <graph drawing> would let us trace each two-<edge> <graph path> as one curve, producing an impossible embedding of $K_{3,3}$. The <graph subdivision> preserves this obstruction. <Kuratowski's theorem> supplies a stronger characterization than these counts.
Back to article page
