A note on the 2-power of Hamilton cycles (Q2142646)

A classical result of \textit{Ø. Ore} [Ann. Mat. Pura Appl. (4) 55, 315--321 (1961; Zbl 0103.39702)] states that if the number of edges in a simple graph on \(n>4\) vertices is at least \(\binom{n-1}{2}+1\), then \(G\) contains a Hamilton cycle unless \(G\) belongs to two sets of exceptional graphs that can be characterized. In this note, the authors extend the result by proving that a graph not containing \(C_n^2\), the square of a Hamilton cycle, has at least \(\binom{n-1}{2}+3\) edges, except when for \(n=8\) and \(n=11\) the lower bound of edges becomes \(25\) and \(49\), respectively. The theorem is proved by carefully identification of the class of all graphs containing \(n-4\) (\(n-5\) when \(n\in \{8,11\}\)) edges that can not be packed together with \(C_n^2\) in \(K_n\), which also helps to determine the extremal graphs for which equality holds.