A cycle of maximum order in a graph of high minimum degree has a chord (Q1684648): Difference between revisions

Summary: A well-known conjecture of \textit{C. Thomassen} [J. Comb. Theory, Ser. B 71, No. 2, 211--214 (1997; Zbl 0905.05047)] states that every cycle of maximum order in a 3-connected graph contains a chord. While many partial results towards this conjecture have been obtained, the conjecture itself remains unsolved. In this paper, we prove a stronger result without a connectivity assumption for graphs of high minimum degree, which shows Thomassen's conjecture holds in that case. This result is within a constant factor of best possible. In the process of proving this, we prove a more general result showing that large minimum degree forces a large difference between the order of the largest cycle and the order of the largest chordless cycle.