5
$\begingroup$

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.

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

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$.

This contradiction proves the claim.

$\endgroup$
  • $\begingroup$ 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$? $\endgroup$ – ctlaltdefeat Feb 20 '15 at 21:05
  • $\begingroup$ 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. $\endgroup$ – Leen Droogendijk Feb 21 '15 at 6:41

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.