Not every 2-tough graph is hamiltonian

Haitze J. Broersma, D. Bauer, H.J. Veldman

Research output: Contribution to journalArticleAcademicpeer-review

51 Citations (Scopus)
78 Downloads (Pure)


We present (9/4-ε)-tough graphs without a Hamilton path for arbitrary >0, thereby refuting a well-known conjecture due to Chvátal. We also present (7/4-ε) -tough chordal graphs without a Hamilton path for any ε>0.
Original languageEnglish
Pages (from-to)317-321
Number of pages5
JournalDiscrete applied mathematics
Issue number99
Publication statusPublished - 2000


  • Toughness
  • Traceable graph
  • Chordal graph
  • Hamiltonian graph
  • 2-tough graph

Fingerprint Dive into the research topics of 'Not every 2-tough graph is hamiltonian'. Together they form a unique fingerprint.

Cite this