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