Chvátal’s toughness conjecture

Remove some junctions from a network and count the separated pieces left behind. A tough network needs many removals to create many pieces. Chvátal asks whether enough toughness always guarantees a round trip visiting every junction once.[1] [2]

Deleting junctions from a network can leave many disconnected pieces. Does one fixed lower bound on removals per remaining piece force a closed route through every junction exactly once, regardless of network size? For a noncomplete finite simple graph, toughness is $\tau(G)=\min |S|/c(G-S)$, where the minimum is over deletions $S$ with at least two components remaining. Complete graphs are assigned $\tau=\infty$. A Hamiltonian cycle visits every vertex once before returning to its start. The conjecture asks for an absolute $t_0$ such that $\tau(G)\geq t_0$ and $|V(G)|\geq3$ imply such a cycle.[1] [2]

“Enough” must mean a single fixed threshold, usable for networks of every size. Recent results find cycles covering almost all vertices when the required toughness grows with size. That leaves both the fixed-threshold and complete-coverage requirements.[1] [2]

Non-Hamiltonian examples rule out thresholds below 9/4. Size-dependent sufficient bounds do not establish a constant. Christoph–Hunter–Sudakov prove a cycle of length (1−o(1))n for t=ω(log³n), whereas Shan–Tanyel prove exact Hamiltonicity for an induced-subgraph-restricted class at toughness 11.[1] [2]

Removing one or more junctions from a round trip cannot leave more separated pieces than junctions removed. That gives a way to rule out a spanning trip by inspecting how a network breaks apart, without trying every route. Toughness asks whether a stronger version of this necessary fragmentation test can become a general guarantee. It connects resistance to splitting with the existence of one complete traversal.[1] [2]

Ordinary vertex connectivity counts how many deletions can disconnect a graph; toughness also counts how many pieces each deletion creates. That distinction matters for a spanning cycle, whose surviving arcs place a simultaneous constraint on the number of pieces after every cut. The conjecture asks whether sufficiently strong fragmentation control can provide a route-existence criterion independent of graph size or a specially forbidden induced subgraph. It connects a family of separation certificates to the global arrangement of all vertices on one cycle.[1] [2]