# Graph with cycles of every length

Prove that in a graph on $n$ vertices with min degree more than $n \over 2$, there are cycles of every length between 3 and $n$ included.

I know that from Dirac's theorem, $G$ has a Hamiltonian cycle, i.e a cycle of length $n$. I'm trying to show that the cycle has enough chords so that there are cycles of every length, but I'm having trouble doing that exactly.

• Until now I can prove the existence of all cycles up to length $\frac{n+4}2$. – Leen Droogendijk Feb 20 '15 at 18:09
• Are you using the general idea of taking the Hamiltonian cycle and using its chords, or something different? – ctlaltdefeat Feb 20 '15 at 18:12
• Using chords in a Hamiltonian cycle, indeed. – Leen Droogendijk Feb 20 '15 at 18:16

Let $v$ be a vertex of $G$. Let $H=G-v$. Then $\delta(H)\geq\frac{n-1}2$ and since $H$ has only $n-1$ elements, $H$ is Hamiltonian, which means that $G$ has an $n-1$-cycle $C$.
Now $v$ has more than $\frac n2$ neighbours, all on $C$, so at least two of them are adjacent, which gives us a triangle and a Hamiltonian cycle.
Let $v_1,\ldots,v_{n-1}$ be the vertices of $C$ and assume there is no cycle of length $t$ for some $3<t<n-1$.
If edge $vv_i$ exists, then edge $vv_{i+t-2}$ (indices $\pmod{n-1}$) cannot exist, since that would produce $t$-cycle $vv_i\ldots v_{i+t-2}v$. But this means that $v$ can have degree at most $\frac{n-1}2$.
• So it's just a matter of counting the chords, I wonder how I couldn't see it...Also, why is taking $v$ out necessary, as opposed to working with an $n$ length cycle $C$? – ctlaltdefeat Feb 20 '15 at 21:05
• My first attack was by using this mechanism using two adjacent vertices on a Hamiltonian cycle, but then these two vertices got in the way, so I could not get further than $\frac{n+4}2$, as mentioned above. It took me quite some time to realize that it could be done with a shorter cycle and a vertex not on that cycle. – Leen Droogendijk Feb 21 '15 at 6:41