A question about the number of chords in a cycle

76 Views Asked by At

Prove that there exists a positive constant $d$, such that for every graph $G$ with minimal degree at least $d$, $G$ contains a cycle $C$ with at least $l$ chords, where $l$ is the length of $C$, and a chord in $C$ is an edge in $G[C]$ but not on $C$.

The proof may need to consider a longest path in $G$ and use Posas’s Rotation Lemma.

Thanks in advance