Thomsen Graph is not Planar

Theorem

The Thomsen graph is not planar.

Proof

Recall the definition of the Thomsen graph:

The Thomsen graph is the complete bipartite graph $K_{3, 3}$:

Recall the definition of planar graph:

A planar graph is a graph which can be drawn in the plane (for example, on a piece of paper) without any of the edges crossing over, that is, meeting at points other than the vertices.

Recall that the complete bipartite graph $K_{2, 3}$ is planar:

Let $A = \set {A_1, A_2, A_3}$ and $B = \set {B_1, B_2, B_3}$ be the two subsets which partition the vertex set of $K_{3, 3}$ which we are to demonstrate non-planarity.

Now we attempt to create $K_{3, 3}$ by building it from its subgraph $K_{2, 3}$, using $\set {A_1, A_2}$ (black) and $\set {B_1, B_2, B_3}$ (white) as the partition of the vertex set of $K_{2, 3}$.

Each of the faces of $K_{2, 3}$ is in the same form as each of the others.

That is, each face consists of $4$ vertices, which is not incident to the $5$th vertex of $K_{2, 3}$.

So exactly where in the plane we place the $6$th vertex does not matter.

Without loss of generality let us place vertex $A_3$ outside the face $A_1 B_1 A_2 B_3$ as shown below:

This face is not incident to $B_2$.

Edges $A_3 B_1$ and $A_3 B_3$ can be constructed without crossing an existing edge of $K_{2, 3}$, as indicated by dotted black lines.

However, it is not possible to construct edge $A_3 B_2$ without crossing one of $A_1 B_1$ or $A_1 B_3$, $A_2 B_1$ or $A_2 B_3$.

This is shown in dotted $\color{red} {\text {red} }$.

Hence the result.

$\blacksquare$

Sources

• 1998: David Nelson: The Penguin Dictionary of Mathematics (2nd ed.) ... (previous) ... (next): graph: 2.
• 2008: David Nelson: The Penguin Dictionary of Mathematics (4th ed.) ... (previous) ... (next): graph: 2.