Can you prove $K_{3,3}$ is not planar without the Jordan Curve Theorem?

Question

The non-planarity of $K_{3,3}$ is well know and e.g. shown here: 3 Utilities | 3 Houses puzzle?

However, it is pointed out that the given proofs all use the Jordan Curve Theorem in one form or another (e.g. Euler's formula).

Hence the question: Can you prove that the utility graph is not planar without using the Jordan Curve Theorem in one form or another or at least prove that that is impossible? Or maybe the non-planarity is even equivalent to the JCT?

I'm asking because I thought it would be interesting.

Answer 1

Carsten Thomassen's article The Jordan-Schonflies Theorem and the Classification of Surfaces does exactly this: starting from the non-planarity of $K_{3,3}$, it proves the Jordan curve theorem.

Here is a part of the proof: this is Proposition 2.6 in the paper, and proves that a Jordan curve leaves the plane in at least two regions. Thomassen also proves at most two, but this is harder and not as self-contained. (Thomassen also proves the non-planarity of $K_{3,3}$ without the full power of the Jordan curve theorem, but I find the proof of Lemma 2.2 extremely unconvincing.)

Let $C$ be a simple closed curve in the plane. Choose:

• $\mathbf p$ to be a point on $C$ minimizing the $x$-coordinate;
• $\mathbf q$ to be a point on $C$ maximizing the $x$-coordinate.

Then $C$ consists of two paths from $\mathbf p$ to $\mathbf q$: call them $P_1$ and $P_2$.

For some intermediate value of $x$ between $\mathbf p_x$ and $\mathbf q_x$, draw a vertical line at that $x$-coordinate. Let $\mathbf r$ and $\mathbf s$ be points of that line lying on $P_1$ and $P_2$ respectively, such that the line segment $[\mathbf r, \mathbf s]$ does not intersect $C$. (The vertical line must intersect both $P_1$ and $P_2$ by the intermediate value theorem; if the intersection point with the highest $y$-coordinate is in $P_1$, choose $\mathbf s$ to be the intersection point in $P_2$ with the highest $y$-coordinate, and $\mathbf r$ to be the intersection point in $P_1$ above $\mathbf s$ with the lowest $y$-coordinate.)

We can find a $\mathbf p, \mathbf q$-path in the plane that does not intersect $C$ anywhere else: for instance, if we take a point $\mathbf a$ with $x$-coordinate lower and $y$-coordinate higher than any point of $C$, and a point $\mathbf b$ with $x$-coordinate higher and $y$-coordinate higher than any point of $C$, then the piecewise linear path from $\mathbf p$ to $\mathbf a$ to $\mathbf b$ to $\mathbf q$ cannot intersect $C$.

Finally, if $C$ does not divide the plane into two regions, pick a point on the $\mathbf p,\mathbf q$-path and a point on $[\mathbf r,\mathbf s]$, and draw a path connecting them that avoids $C$. Let $\mathbf t$ be the last point of the $\mathbf p, \mathbf q$-path on that path, and let $\mathbf u$ be the first point after $\mathbf t$ of the segment $[\mathbf r, \mathbf s]$ on that path.

Now we have a planar embedding of $K_{3,3}$ with vertices $\mathbf p, \mathbf q, \mathbf u$ in one part of the bipartition and vertices $\mathbf r, \mathbf s, \mathbf t$ in the other part.