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.
Can we draw a graph with only cycles of length 5 through 9 with only 9 vertices?.
graph theory
Related Solutions
If you have an $n$-vertex graph with $n$ or more edges, there must be a cycle. You can calculate the number of edges from the degree sequence using the Handshaking Lemma.
If the $n$-vertex graph has $n-1$ or fewer edges, provided there are two vertices of degree $2$ or more, it may contain a cycle (or it may not). For example, these two graphs have the same degree sequences but only the first one has a cycle:
If you also knew the number of components $c(G)$ of the graph $G=(V,E)$ you could determine whether or not there is a cycle. Specifically, a graph is acyclic if and only if $c(G)=|V|-|E|$.
Hint: Draw a cycle of length 9. Can you see how to build a 6-cycle and a 7-cycle with the extra vertex? Now remains to build the 5-cycle and the 8-cycle. You can build the 5-cycle by adding only 1 edge. I hope this can help you without giving you the solution straight away!
Best Answer
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:
Now, it is easy to check all the remaining cases, and none of them produce all five cycle lengths we want.