Prove that $K_{3,3}$ is not planar.

Question

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?

Answer 1

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$

Answer 2

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.

Answer 3

Proof:

Let $G = (V, E)$ be an isomorphism of $K_{3, 3}$ such that $V = \{ v_1, v_2, v_3, v_4, v_5, v_6\}$ and $E = \{ \{v_i, v_j\} : i \in \{1, 2, 3\}, j \in \{4, 5, 6\}\}$. Without loss of generality, let $G' = (V', E')$ be a subgraph of $G$ isomorphic to $K_{2, 2}$ such that $V' = \{ v_1, v_2, v_4, v_5 \}$ and $E' = \{ \{ v_i, v_j \} : i \in \{1, 2\}, j \in \{4, 5\} \}$. $G'$ is, of course, planar as the planar drawing of $G'$ is a Jordan curve, $\gamma$, in the plane made up of the arcs $\alpha (1, 4), \alpha (1, 5), \alpha (2, 4), \alpha (2, 5)$. $\gamma$ induces an interior and exterior region. By the Jordan curve theorem, both $v_3$ and $v_6$ must be in the same region. That is, $v_3$ and $v_6$ are both located in either the interior region or exterior region of $\gamma$ (otherwise, the arc $\alpha (3, 6)$ would intersect at least one of the arcs that make up $\gamma$ and $G$ would not be planar).

Case 1: $v_3$ is in the interior region of $\gamma$. This results in a division of the interior region of $\gamma$ into $2$ different regions, which we'll call $R_{1}$ and $R_{2}$. We'll also denote the unbounded region by $R_3$. Without loss of generality, a possible drawing of this is shown below:

If $v_6$ is in $R_1$, then the arc $\alpha (2, 6)$ cannot be formed without intersecting at least one arc $\alpha \in \{ \alpha (i, j) : i \in \{1, 2, 3\}, j \in \{4, 5\}\}$. Similarly, if $v_6$ is in $R_2$, then the arc $\alpha (1, 6)$ cannot be formed without intersecting at least one arc $\alpha \in \{ \alpha (i, j) : i \in \{1, 2, 3\}, j \in \{4, 5\}\}$. Hence, a contradiction.

Case 2: $v_3$ is in the exterior region of $\gamma$. This still results in the same number of regions, which can be confirmed by a drawing the graph or Euler's formula for planar graphs. Without loss of generality, a possible drawing is shown below.

If $v_6$ is in $R_1$, then the arc $\alpha (2, 6)$ cannot be formed without intersecting at least one arc $\alpha \in \{ \alpha (i, j) : i \in \{1, 2, 3\}, j \in \{4, 5\}\}$. Similarly, if $v_6$ is in $R_2$, then the arc $\alpha (3, 6)$ cannot be formed without intersecting at least one arc $\alpha \in \{ \alpha (i, j) : i \in \{1, 2, 3\}, j \in \{4, 5\}\}$. Hence, a contradiction.

Thus, $K_{3,3}$ cannot be drawn without at least one arc intersection and is not planar.