Prove that $K_{3,3}$ is not planar.
This problem comes from A Course in Combinatorics (Problem 1D). At this point, the authors have introduced merely the most basic concepts of graphs, so this is preferably solved without other results. The hint says: "Call the vertices $a_1,a_2,a_3$ and $b_1,b_2,b_3$. First, omit $a_3$ and show that there is only one way to draw the graph with the remaining $6$ edges in the plane." But how am I supposed to show that there is only one way to draw the graph, since even the locations of the points themselves are arbitrary?
Best Answer
If you have proved the Euler characteristic of the plane, this can be used for a slicker proof.
Euler's equation $V-E+F=2$ implies that a planar drawing of a graph with $6$ vertices and $9$ edges must have exactly $5$ faces (including the infinite "outside" face).
$K_{3,3}$ is simple, so no face has two sides, and bipartite, so every face has an even number of sides. Thus every face must have at least $4$ sides. But the sum of sides over all the faces is twice the number of edges (each edge is a side of exactly two faces), so this says that $2E\ge 5\cdot 4=20$. But actually $2E$ is $18$, a contradiction.