SOLVED
This has been resolved in some other way than a proof or disproof.
Let $k\geq 0$. Let $f(k)$ be such that every graph on $n\geq f(k)$ vertices with at least $\binom{n-k-1}{2}+\binom{k+2}{2}+1$ edges contains a cycle on $n-k$ vertices. Determine or estimate $f(k)$.
Erdős
[Er62e] proved that $f(k)$ exists for all $k\geq 0$; this is not immediately stated in
[Er62e], but Cambie has in the comments explained why the existence of $f(k)$ follows from the result of
[Er62e].
Ore
[Or61] proved that $f(0)=1$, in other words, every graph on $n\geq 1$ vertices with at least $\binom{n-1}{2}+2$ edges contains a Hamiltonian cycle on $n$ vertices.
Bondy
[Bo71b] proved that $f(1)=1$.
Woodall
[Wo72] proved that every graph on $n\geq 2k+3$ vertices with at least $\binom{n-k-1}{2}+\binom{k+2}{2}+1$ edges contains a cycle on $l$ vertices for all $3\leq l\leq n-k$. This settles this question completely.
View the LaTeX source
This page was last edited 28 December 2025. View history
|
Likes this problem
|
None
|
|
Interested in collaborating
|
None
|
|
Currently working on this problem
|
None
|
|
This problem looks difficult
|
None
|
|
This problem looks tractable
|
None
|
|
The results on this problem could be formalisable
|
None
|
|
I am working on formalising the results on this problem
|
None
|
Additional thanks to: Alfaiz and Stijn Cambie
When referring to this problem, please use the original sources of Erdős. If you wish to acknowledge this website, the recommended citation format is:
T. F. Bloom, Erdős Problem #1012, https://www.erdosproblems.com/1012, accessed 2026-04-11
