We show that every graph G on n vertices with minimal degree at least n/k contains a cycle of length at least [n/(k − 1)]. This verifies a conjecture of Katchalski. When k = 2 our result reduces to the classical theorem of Dirac that asserts that if all degrees are at least 1/2n then G is Hamiltonian.
All Science Journal Classification (ASJC) codes
- Discrete Mathematics and Combinatorics
- Geometry and Topology