[Math] Is the complement of a C7 graph planar or non-planar

graph theoryplanar-graphs

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

Complement of a C7

Best Answer

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.

Related Question