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?
$\endgroup$2 Answers
$\begingroup$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.
$\endgroup$ 3 $\begingroup$The edges cannot cross, so if you take $a_1, a_2, b_1, b_2$ you get a quadrilateral. The only choice that you have is that you can put $a_3$ and $b_3$ either outside or inside, which gives you at most 4 cases (actually inside and outside are symmetric so you can reduce the number of cases, but you don't have to use that).
Another way to look at this is: take any planar embedding of your graph, and take a subgraph on $a_1,a_2,b_1,b_2$. It will give you a quadrilateral, so let this quadrilateral of yours (from the previous paragraph) represent the one from the embedding. Now, the embedding could have put $a_3$ and $b_3$ either inside or outside, and so on...
Finally you will get that wherever you would like to put in $b_3$ (one case for each face of the graph on $a_1,a_2,a_3,b_1,b_2$), you cannot draw all the edges without crossing, thus the initial embedding could not exist.
I hope this helps $\ddot\smile$
$\endgroup$ 6
