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

  • $\begingroup$ 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. $\endgroup$ – almagest Nov 30 '19 at 13:55
  • $\begingroup$ 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. $\endgroup$ – D_mathematician Nov 30 '19 at 14:25

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.

enter image description here

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.

| cite | improve this answer | |
  • $\begingroup$ I don't know why I didn't recognise that cycle of octagon (as well as all others cycles) must be a closed curve on the plane. Of course every cycle is planar graph so it must be drawn like this (closed curve). The rest is great conclusion of this fact. $\endgroup$ – D_mathematician Nov 30 '19 at 14:45

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.