We build a graph G as follows:
Vertices of G are vertices of regular octagon and edges of G are sides of this octagon and it's 4 longest diagonals (which are linking opposite vertices).
I have to show that G isn't planar without using Kuratowski theorem (with this theorem it's kind of easy, because it's not hard to notice that G is subdivide of graph K(3,3)).
Given graph G have 8 vertices and 12 edges. What's more this graph don't have cycles of length 3, so I was hoping that conclusions of Eulers formula will help, but 2*n-4=12 (where n is a number of vertices), so there is no contradiction (and I can't do more with Eulers formula, becouse our graph have cycles of length 4).
I'm stuck with this problem now but I find it very interesting.
Is there any criterium witch will help me with that problem? I found very interesting one that if graph of order 6 or more have 3 spanning trees such that every edge of graph belongs to exactly one of those spanning trees, then graph is non planar (but its not helping me with my example, cause on graph with 8 vertices I will need 21 or more edges to use this theorem).
I will be thankful for any other criteria (or explanation) of (non)planarity (which is not using the Kuratowski theorem), especially for one witch will help me with my exercise 😉
Best Answer
One alternative is to just attempt to construct a planar embedding of the graph and show that it is impossible by the Jordan curve theorem.
To that end, you start with the cycle of the octagon $\mathscr C=(A,B,C,D,E,F,G,H,A)$, which must be a closed curve on the plane. Now, you must add an edge $AC$, which will either pass through the interior or the exterior region defined by $\mathscr C$. I will cover the case where it goes through the interior. Then $CG$ must pass through the exterior of $\mathscr C$, leaving us with the following diagram.
Now, consider the curve associated with the cycle $\mathscr C'=(A,B,C,G,F,E,A)$. $D$ is on the interior of $\mathscr C'$ and $H$ is on the exterior, so there is no way for a curve connecting those two points to avoid crossing $\mathscr C'$.
As the other case where $AE$ is on the exterior face is similarly dismissed, it follows that there is no planar embedding of the graph.