Not every 2-tough graph is Hamiltonian (Q1962051)

A long standing conjecture due to V. Chvátal was that any \(2\)-tough graph is Hamiltonian. A very clever example is presented that disproves this conjecture. More specifically, it is shown for any \(\epsilon > 0\), there is a \((9/4 - \epsilon)\)-tough graph that does not contain a Hamiltonian path. In lack manner a \((7/4 - \epsilon)\)-tough chordal graph that has no Hamiltonian path is presented. The latter result gives a lower bound to the toughness that will imply Hamiltonian in chordal graphs as opposed to the upper bound of \(18\) of \textit{G. Chen, M. S. Jacobson, A. Kézdy} and \textit{J. E. Lehel} [Networks 31, No. 1, 29-38 (1998; Zbl 0894.90150)].