Lollipops, dense cycles and chords

Abstract

In 1980, Gupta, Kahn and Robertson proved that every graph $G$ with minimum degree at least $k\ge 2$ contains a cycle $C$ containing at least $k+1$ vertices each having at least $k$ neighbors in $C$ (so $C$ has at least $\frac{(k+1)(k-2)}{2}$ chords). In this work, we go further by showing that some of its edges can be contracted to obtain a graph with high minimum degree (we call such a minor of $C$ a \emph{cyclic minor}). We then investigate further cycles having cliques as cyclic minors, and show that minimum degree at least $O(k^2)$ guarantees a cyclic $K_k$-minor.

Added explanations, mostly about the application of Marcus Tardos Theorem