Claims

../

1961_12_01_ore: Ore (Ann. Mat. Pura Appl. 1961), Theorem 4.3: a graph on n vertices with at least binom(n-1,2) + 2 edges has a Hamilton circuit, sharp by K_{n-1} with a pendant edge; this gives f(0) = 1; refereed.

1971_09_01_bondy: Bondy (Discrete Math. 1971), Theorem 2: a graph of order n and size at least (n^2 - 5n + 14)/2 = binom(n-2,2) + 4 has a cycle of length n - 1, sharp for n > 4; this gives f(1) = 1; refereed.

1972_05_01_woodall: Woodall's Corollary 11.1 (Proc. London Math. Soc. 1972) gives, on n at least 2k + 3 vertices with the problem's edge count, a circuit of every length from 3 to n minus k: f(k) is at most 2k + 3, the count sharp there.

---