While working through some problems concerning planarity, I encountered one asking me to prove that every graph with at most three cycles is planar. Being rather elementary in my knowledge of Graph Theory, I have tried approaching this through use of Kuratowski's Theorem:

A finite graph is planar if and only if it does not contain a sub-graph that is homeomorphic to $K_5$ or $K_{3,3}$.

However, from what I have observed $K_{3,3}$ has 10 cycles. In this way, recognizing that neither isolating a sub-graph nor subdividing said sub-graph can create new cycles, it would appear that a graph would need at least 10 cycles to be non-planar. I have been unable to identify any graph with fewer than ten cycles which proves non-planar. Any help as to what I am missing here would be greatly appreciated. Thanks!

  • 1
    $\begingroup$ Without thinking too hard about the problem itself, one possibility is that the problem isn't asking you to prove an optimal statement. If it is true that any graph with fewer than 10 cycles is planar (I don't know yet if it is!), it is certainly also true that any graph with at most 3 cycles is planar. $\endgroup$ – Misha Lavrov Dec 10 '18 at 5:40
  • $\begingroup$ Are you sure $K_{3,3}$ has only $10$ cycles? I count $9$ cycles of length $4$ and a bunch ($6$?) of cycles of length $6$. $\endgroup$ – bof Dec 10 '18 at 5:41
  • $\begingroup$ I don't know what you're worried about. The problem is asking you to prove that every nonplanar graph has more than $3$ cycles, right? If you're allowed to use Kuratowski's theorem, then all you have to do is prove that $K_{3,3}$ and $K_5$ (and of course their subdivisions) have more than $3$ cycles. Looks like you've already done this for $K_{3,3}$ and $K_5$ should be just as easy if not easier. $\endgroup$ – bof Dec 10 '18 at 5:43
  • $\begingroup$ @MishaLavrov I was thinking along a similar line. However, after looking more carefully at the book I believe the an optimal solution is required $\endgroup$ – Katacka Dec 10 '18 at 6:14
  • $\begingroup$ @bof After recounting, I am fairly certain there are 15. I also found there to be 9 cycles of length 4, but only 5 cycles of length 6. $\endgroup$ – Katacka Dec 10 '18 at 6:23

Your Answer

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

Browse other questions tagged or ask your own question.