Math Conjectures

Chvátal's Toughness Conjecture

OPENMajorConjectureProposed 1973 · Standard version

Canonical statement

There exists a real constant t0>0t_0>0 such that every finite simple t0t_0-tough graph on at least three vertices is Hamiltonian. Here GG is tt-tough if, for every vertex set SS with c(G−S)>1c(G-S)>1,
∣S∣≥t c(G−S), |S|\geq t\,c(G-S),
where G−SG-S is the graph obtained by deleting SS and c(⋅)c(\cdot) denotes the number of connected components.
View source LaTeX
There exists a real constant \(t_0>0\) such that every
finite simple \(t_0\)-tough graph on at least three vertices is
Hamiltonian. Here \(G\) is
\(t\)-tough if, for every vertex set \(S\) with
\(c(G-S)>1\),
\[
  |S|\geq t\,c(G-S),
\]
where \(G-S\) is the graph obtained by deleting \(S\) and
\(c(\cdot)\) denotes the number of connected components.
GRAPH-022:[Chvatal1973Tough][BauerEtAl1990Tough][Nikoghosyan2012Toughness]
Graph theoryCombinatorics

Notes

The toughness of a graph measures how robustly it holds together: GG is tt-tough if every vertex set SS whose deletion disconnects the graph satisfies ∣S∣≥t c(G−S)|S|\ge t\,c(G-S), where c(G−S)c(G-S) counts the components left behind. A Hamiltonian graph is easily seen to be 11-tough, since removing SS from a spanning cycle leaves at most ∣S∣|S| pieces. In 1973 Chvátal conjectured a converse of sorts: there is an absolute constant t0t_0 such that every t0t_0-tough graph on at least three vertices is Hamiltonian [Chvatal1973Tough].

The natural first guess t0=2t_0=2 fails: Bauer, Broersma, and Veldman constructed non-Hamiltonian graphs that are 22-tough [BauerEtAl1990Tough], and further families of non-Hamiltonian graphs of high toughness have been analyzed [Nikoghosyan2012Toughness]. In the positive direction, sufficiently tough graphs are known to admit strong spanning structures, and toughness thresholds forcing Hamiltonicity have been established within special graph classes.

No absolute threshold valid for all graphs is known, so the conjecture remains open; resolving it requires either a universal constant t0t_0 or non-Hamiltonian graphs of arbitrarily high toughness.

References (3)

The boxed statement is the canonical open formulation — not a stronger variant or a related research program. The status reflects the catalog's last review; do your own literature search before investing serious effort.