Is the complement of a C7 graph planar or non-planar?

Question

I am trying to prove whether the complement of a cycle-7 graph is planar or non-planar. I tried to use Euler's theorem to prove it;

In a connected simple planar graph with v vertices and e edges, if v ≥ 3, then e ≤ 3v−6.

I have that the complement of a C7 has 7 vertices and 14 edges.. Plugging this into Euler's theorem this comes out as 14 ≤ 15, which obviously holds, so this method does not prove non-planarity. I've also tried to find K5 and a K3,3 as subgraphs but also had no luck there either.

Any helpful tips on how to go about it from here?

I've included a photo of the only version of the complement of C7 I could find, apologies for the vertices being labelled as weekdays. I just wanted to show the graph more than anything

Answer 1

It's not planar. We have the Hamilton cycle Sunday-Tuesday-Thursday-Saturday_Wednesday-Monday-Friday-Sunday, to use the labeling in your picture. There is an edge from Sunday to Wednesday and an edge from Tuesday to Friday. If these are both drawn inside the cycle, or both out side, they would cross, so suppose the Sunday-Wednesday edge in inside the cycle and the Tuesday-Friday edge outside. Then the Sunday-Thursday edge must also be inside and the Tuesday-Saturday edge must be outside. Now there is no way to draw the Thursday-Wednesday edge.

Answer 2

Merge the days Sunday & Wednesday call this node Suwday. Now Suwday, Monday, Tuesday $\color{blue}{3}$ and Thursday, Friday, Saturday $\color{red}{3}$ will need to form a $K_{\color{blue}{3},\color{red}{3}}$.

And thus by Kuratowski's Theorem https://en.wikipedia.org/wiki/Kuratowski%27s_theorem the original graph cannot be planar.

Answer 3

While the question is perfectly answered by citing the Kuratowski theorem, it is amusing to note that this workday graph actually defines a Moebius strip. You can build it with paper consisting of 7 triangles. The fact that it is not planar can be seen now as a consequence that it is not possible to ``flatten" the Moebius strip: it would provide an orientation, but the Moebius strip is non-orientable. Picture of Workday graph as Moebius strip