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

redrawing UG graph

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.

apply jordan curve theorem

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):

Graph X

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,

Graph X pseudoproof

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:

Graph X redrawn

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)

  • $\begingroup$ The proof starts by ensuring that the configuration is constrained. Your pseudo-proof omits that step. (I think the clearest proof uses $F-E+V=2$) $\endgroup$ – Mark Bennet Jun 26 '19 at 16:50
  • $\begingroup$ @MarkBennet What does it mean for a configuration to be "constrained" and why does that ensure that no other configuration can avoid edge-crossings? $\endgroup$ – Cardioid_Ass_22 Jun 26 '19 at 16:52
  • $\begingroup$ In the first configuration the first observation is that either the outside or the inside of the hexagon has to contain at least two of the additional edges. No such observation can be made about the second configuration. The problem of determining whether any configuration under consideration can be distorted to hexagonal form is avoided by using the Euler number, which is why I prefer it. $\endgroup$ – Mark Bennet Jun 26 '19 at 17:25
  • $\begingroup$ @MarkBennet I understand why you suggest using Euler's formula, but, given that it seems you understand the proof, could you please elaborate a bit? Why does the observation of two edges being either inside or outside the hexagon mean that any configuration must have an edge-crossing? To avoid an overlong discussion in the comments, also, could you direct me to any sources that deal with this method of proof in more detail? $\endgroup$ – Cardioid_Ass_22 Jun 26 '19 at 18:02

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.

  • $\begingroup$ "Other configurations yield to a similar argument." Yes, but the whole question is about why this is true. I understand the argument for the hexagonal configuration. Why does the proof for the hexagonal configuration also demonstrate nonplanarity of all other configurations? $\endgroup$ – Cardioid_Ass_22 Jun 26 '19 at 20:30
  • $\begingroup$ @Cardioid_Ass_22 I was addressing your comment why the two edges inside or outside makes a difference. You don't have the same constraint in your other example - the two additional vertices can be both inside, both outside or one inside and one out. As to why the hexagon works, the maximal cycle on the six points is clearly of length six, and this must exist and must be non-intersecting if the graph is planar - so you must have a non-intersecting hexagon. It doesn't matter how you draw it, because the vertices remain in the same order and there is the same relationship of outside to inside. $\endgroup$ – Mark Bennet Jun 26 '19 at 21:29
  • $\begingroup$ Are you saying that, for any supposed intersectionless drawing of the $UG$, we'll always be able to delete three edges so that the remaining graph is isomorphic to $C_6$? If so, how do we show this? (this is basically what my question is about - the exact details of why the proof in the question works for any drawing) $\endgroup$ – Cardioid_Ass_22 Jun 27 '19 at 15:24
  • 1
    $\begingroup$ @Cardioid_Ass_22 $AYCZBXA$ will always make an intersection less hexagon as will $AXBYCZA$ or any sequence with alternating vertices from $ABC$ and $XYZ$ - this works because the graph is a complete bipartite graph, and the vertices split into two sets of three in this natural way and every point from the first set is joined to every point in the second. It will be a hexagon because it has six sides, and intersectionless because it is a subgraph of an intersectionless graph. $\endgroup$ – Mark Bennet Jun 27 '19 at 15:56

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.