The longest cycle of a graph with a large minimal degree

Research output: Contribution to journalArticlepeer-review

10 Scopus citations


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.

Original languageEnglish (US)
Pages (from-to)123-127
Number of pages5
JournalJournal of Graph Theory
Issue number1
StatePublished - 1986
Externally publishedYes

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Geometry and Topology


Dive into the research topics of 'The longest cycle of a graph with a large minimal degree'. Together they form a unique fingerprint.

Cite this