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

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.

• 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. – Misha Lavrov Oct 25 '18 at 20:13
• 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. – Reza Fallah Moghaddam Oct 25 '18 at 20:17
• Hm. Maybe it is not possible. – Misha Lavrov Oct 25 '18 at 20:35
• can we prove it? It seems that it is impossible. – Reza Fallah Moghaddam Oct 25 '18 at 20:38
• There's the casework approach I've outlined below. Maybe there's another argument possible, too. – Misha Lavrov Oct 25 '18 at 20:44

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.