# Showing that graph build on octagon isn't planar

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

• Why don't you want to use the Kuratowski theorem, from which the result follows immediately. Label the points 1,...,8 in order, so that we have edges between $i,i+1$ and $i,i+4$ (reducing by 8 where necessary). Then take the two sets $A=\{1,4,6\}$ and $B=\{2,5,8\}$. There is an edge between every point of $A$ and every point of $B$ except that we have 2-3-4 instead of 2-4, and 6-7-8 instead of 6-8. Since $K_{3,3}$ is not planar, nor is this graph. – almagest Nov 30 '19 at 13:55
• Like I wrote in question I know that with Kuratowski theorem the problem is easy to solve. It's an exercise from some graph theory course to solve this problem without Kuratowski theorem and I find it very interesting how to solve it this way. – Denis Zelent Nov 30 '19 at 14:25

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.