Can we draw a graph with only 9 vertices with only cycles of length 5 through 9 ?

Draw a connected graph having exactly 9 vertices that has at least one cycle of each length from 5 through 9, but has no cycles of any other length.

  • $\begingroup$ Try it yourself first. Draw a $9$-vertex graph with a $9$-cycle, try adding some more edges to it to get the other cycles, and if you get stuck, then it will do you any good to ask for help. $\endgroup$ – Misha Lavrov Oct 25 '18 at 20:13
  • $\begingroup$ It is easy for me to draw a 9-vertex graph with cycles of length 5,6,7,9. But I can not find a cycle of length 8. $\endgroup$ – Reza Fallah Moghaddam Oct 25 '18 at 20:17
  • $\begingroup$ Hm. Maybe it is not possible. $\endgroup$ – Misha Lavrov Oct 25 '18 at 20:35
  • $\begingroup$ can we prove it? It seems that it is impossible. $\endgroup$ – Reza Fallah Moghaddam Oct 25 '18 at 20:38
  • $\begingroup$ There's the casework approach I've outlined below. Maybe there's another argument possible, too. $\endgroup$ – Misha Lavrov Oct 25 '18 at 20:44

Both trying to find such a graph and proving that it does not exist can be done by casework.

Start with the $9$-cycle, since there is only one way it can look. We need to add more edges to get more cycle lengths, and all options so far are equivalent: we connect two vertices at distance $4$ around the cycle.

If we add an arbitrary one of these edges, then several other options can be eliminated since they'd create a short cycle. All our remaining choices are drawn in red below:

edge options cycles

Now, it is easy to check all the remaining cases, and none of them produce all five cycle lengths we want.


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.