Toughness Counterexample

How to contact me.
[Un]solved problem 21, from Bondy and Murty's list.

D. Bauera, H.J. Broersmab, and H.J. Veldmanb. Not every 2-tough graph is Hamiltonian. Discrete Applied Mathematics 99(2000), 317-321. © 2000 Elsevier Science B.V. All rights reserved. PII: S0166-218X(99)00141-9

aDepartment of Mathematical Sciences, Stevens Institute of Technology, Hoboken, NJ 07030, USA
bFaculty of Mathematical Sciences, University of Twente, P.O. Box 217, 7500 AE Enschede, The Netherlands

Received 19 June 1997; received in revised form 27 January 1998; accepted 9 March 1999

The first two authors dedicate this paper to the memory of their dear friend and coauthor Henk Tau Veldman, who died October 12, 1998.


We present (9/4 - e)-tough graphs without a Hamilton path for arbitrary e>0, thereby refuting a well-known conjecture due to Chvátal. We also present (7/4 - e)-tough chordal graphs without a Hamilton path for any e>0.

MSC: 05C45; 05C38; 05C35

Keywords: Hamiltonian graph; Traceable graph; Toughness; 2-tough graph; Chordal graph
Last modified April 30, 2000, by S.C. Locke.