Proving that drawing a complete graph with more than four vertices requires at least two edges to cross and generalizing in higher dimensions

Question

Drawing a complete graph with four vertices or less such that no edges cross is trivial. I conjecture, and would like to prove, that it is impossible with five. This is what I've come up with:

The only way to draw a complete graph with three vertices $A$, $B$ and $C$ is to draw a triangle $ABC$ (fig. 1).

Fig 1: Triangle $ABC$

The only way to draw a complete graph with four vertices is to add a vertex $D$ inside or outside of $ABC$ (fig. 2).

Fig 2: possible positionings of $D$

In any case, we can rename the vertices, which results in an outer triangle $EFG$ containing $H$, split into three smaller triangles $EFH$, $FGH$ and $GEH$.

To create a complete graph with five vertices, we must add a vertex $I$ inside $EFH$, $FGH$ or $GEH$, or outside of $EFG$. In all cases, the edge linking $I$ to the vertex not in the aforementioned triangles (respectively $G$, $E$, $F$ and $H$) must cross at least one other.

This "proof" feels unnecessarily long-winded, and maybe not very rigorous. Can anyone suggest a more efficient one?

Furthermore, this is the two-dimensional case. It seems obvious to me that in more dimensions, as long as you avoid having five vertices on the same plane, the edges should never need to cross; but is there a way to prove that?

Answer 1

You can prove that $K_5$ is non-planar by using Euler's Formula. If it were planar, then we'd have $V-E+F=2$. We also know that $V=5$, that $E=5*4/2=10$. But we also know that all the faces must be triangular (else you could add a diagonal edge through the face), so we have $3F=2E$. It is then easy to show that this system of equations has no solution.

So $K_5$ is non-planar. $K_n$ for all larger $n$ contains copies of $K_5$, so must be non-planar too.

As for embedding it in 3D without intersections:
If you had two edges intersecting, then the four end points would lie in a plane. So all you have to do is avoid having four points lying in a plane.
Suppose you have a non-intersecting embedding for $K_n$. Consider all the planes that go through any three of those points. There are $\binom{n}{3}$ ways to choose three of the points, so the same number of such planes. Now add any point that does not lie on any of those planes (a finite number of 2d planes cannot cover all of 3d space), and you can construct $K_{n+1}$ without intersections.

Answer 2

In fact, $K_n$ can be seen as being the edge skelleton of the $(n-1)$-dimensional regular simplex. That one clearly is convex. Therefore it becomes obvious that this then would be a realization without any intersections.

--- rk