I have, while reading material on introductory graph theory, frequently come across a specific proof of the nonplanarity of the $UG$ (and an analogous one for the nonplanarity of $K_5$) that uses the Jordan curve theorem and goes like this:
First, we consider the version of the $UG$ where all edges are straight lines. We rearrange the vertices so that they lie in a hexagonal formation and, then, delete all edges lying inside the newly formed hexagon, like so
Then, we try and draw the previously deleted edges back into the graph while avoiding edge-crossings. Since there were three deleted edges, we must have that either $\geq 2$ edges are inside the hexagon or $\geq 2$ are outside the hexagon. With the aid of the Jordan Curve theorem, it is easy to show that either possibility necessarily results in at least one edge crossing.
The proof then concludes that this shows that the $UG$ is nonplanar.
My question is, how do we know that the necessity of edge crossings doesn't just arise from the original configuration that was selected, i.e. having the vertices arranged in a hexagon with no additional edges? Nonplanarity requires that, no matter how the vertices are arranged and the edges drawn, at least one edge crossing will result – what if, upon beginning from a different configuration of points and edges, we could avoid an edge-crossing?
Perhaps as an example to make my question more concrete, consider the following graph, graph $X$ (the butterfly graph):
If we are in doubt of its planarity, we may very easily construct a pseudoproof for nonplanarity along the same lines as the one for the $UG$. We delete the edge connecting $4$ and $5$, and, using the Jordan curve theorem,
we can demonstrate the inevitability of an edge-crossing. Of course, in this case, this line of reasoning has led us astray, because graph $X$ can be redrawn as:
which is obviously planar. So it seems that the initial configuration of vertices and edges does matter. Why does it not affect the result in the above proof for $UG$'s nonplanarity?
(note: the first two images come from this webpage)
Best Answer
To explain the first proof. Once you have the hexagon, assume that there are at least two edges outside the hexagon. Since all the edges are alike let's make $AZ$ one of the two.
As you have drawn it points $Y$ and $C$ are inside the quadrilateral $AZBX$ and starting an edge at $X$ or $B$ which runs outside the hexagon means that the edge contains a point outside the quadrilateral. The boundary of the quadrilateral is a Jordan curve, and the line must cross its boundary to reach the relevant point ($Y$ or $C$) inside.
Other configurations yield to a similar argument.