Mimimum Degree and the Number of Chords

Abstract

We address the following problem: What minimum degree forces a graph on \(n\) vertices to have a cycle with at least \(c\) chords? We prove that any graph with minimum degree \(\delta\) has a cycle with at least \(\frac{(\delta+1)(\delta-2)}{2}\) chords. We investigate asymptotic behaviour for large \(n\) and \(c\) and we consider the special case where \(n = c\).