Chvátal's Toughness Conjecture

Chvátal’s Toughness Conjecture

Definitions and mathematical statement

Shared notation.

Unless a section says otherwise, ${\mathbb{N}}=\{1,2,\ldots\}$, ${\mathbb{Z}}$ is the ring of integers, ${\mathbb{Q}},{\mathbb{R}},{\mathbb{C}}$ are the rational, real, and complex fields, $[N]=\{1,\ldots,\lfloor N\rfloor\}$, and $\log$ is the natural logarithm. For real functions of a parameter tending to infinity, $f\ll g$ and $f=O(g)$ mean $|f|\leq Cg$ eventually for some fixed $C$; $f\gg g$ reverses this comparison; $f=o(g)$ means $f/g\to0$; $f\sim g$ means $f/g\to1$; and $f\asymp g$ means both order bounds. A subscript on $O$ or $\ll$ specifies allowed constant dependence. The expression $n^{o(1)}$ in an upper bound means growth smaller than $n^\epsilon$ for each fixed $\epsilon>0$. Local definitions govern any exception, finite-field convention, or use of the same symbol for another object. An asymptotic claim is not automatically an effective algorithm.

For $t>0$, a finite graph $G$ is $t$-tough if $|S|\geq t\,c(G-S)$ for every vertex set $S$ whose deletion produces at least two components; $c$ counts components. Complete graphs have infinite toughness by convention. Seek one absolute $t$ such that every $t$-tough graph with at least three vertices has a Hamiltonian cycle. [S1] [S2]

Statement recorded in the supplied source.

Is there a constant t such that every t-tough graph is Hamiltonian? [S1]

Residual task reported by the archive.

The embedded review $2026-08-17$ records: Prove a finite universal threshold or construct non-Hamiltonian graphs of arbitrarily large toughness. [S1]

Short English statement

Can a sufficiently strong uniform resistance to being split into components guarantee a spanning cycle?

Research attempt

Quantifiers and plan of attack.

The desired threshold must be independent of the number of vertices, and a negative solution must give non-Hamiltonian graphs with unbounded toughness. A single tough non-Hamiltonian graph only excludes some possible thresholds. The primary source [E1] concerns graphs with a specific forbidden induced subgraph, so its extra hypothesis cannot be discarded. Here the approach is to derive necessary inequalities and measure exactly what an explicit obstruction rules out.

Hamiltonicity implies one-toughness.

Suppose $G$ has a spanning cycle and $S$ is a nonempty vertex set. Deleting $|S|$ vertices from that cycle leaves at most $|S|$ nonempty path components. The remaining edges of $G$ can join these components but cannot split one. Hence whenever $c(G-S)\ge2$, \[ c(G-S)\le |S|. \] Thus every Hamiltonian graph is one-tough. Reversing this implication is not justified; the condition records how many pieces cuts produce, not how a spanning cycle can traverse each piece.

What a large toughness value forces.

Let $G$ be $t$-tough and noncomplete. Any separating set produces at least two components, so its size is at least $2t$. In particular the vertex connectivity is at least $\lceil2t\rceil$. If a vertex $v$ has a nonneighbour, deleting $N(v)$ leaves $v$ isolated and at least one further vertex. Therefore $d(v)\ge2t$. A minimum-degree vertex in a noncomplete graph has a nonneighbour, yielding \[ \delta(G)\ge2t. \] For an independent set $I$ of size $\alpha\ge2$, delete its complement. The remaining graph has exactly $\alpha$ components, so \[ n-\alpha\ge t\alpha, \qquad \alpha\le\frac n{t+1}. \] These are rigorous restrictions, but for fixed $t$ the degree lower bound is constant while $n$ is unbounded. They therefore do not imply a condition of the form $\delta\ge n/2$. Substituting a Hamiltonian theorem requiring a degree bound proportional to $n$ would leave a quantifier gap.

A family showing why thresholds below one fail.

For $1\le a\le b$ and $b\ge2$, the complete bipartite graph $K_{a,b}$ can be disconnected only by deleting all vertices of one side, since any surviving vertices on both sides induce a connected graph. Deleting the side of size $a$ produces $b$ isolated vertices and ratio $a/b$. If additional vertices of the other side are deleted, the ratio becomes $(a+r)/(b-r)\ge a/b$ whenever at least two vertices remain. Deleting the other side first gives ratios at least $b/a\ge a/b$ when that deletion is a qualifying cut. Thus its toughness is exactly $a/b$.

A bipartite cycle visits equally many vertices in the two parts, so $K_{a,b}$ is Hamiltonian exactly when $a=b\ge2$. In particular $K_{r,r+1}$ is non-Hamiltonian and has toughness $r/(r+1)$, tending to one from below. For every $t<1$, some member is $t$-tough and non-Hamiltonian. This excludes all those thresholds, but the sequence is bounded and gives no disproof of the existence of a larger threshold.

An exact obstruction above one.

Use the Petersen graph on the ten two-element subsets of $\{0,1,2,3,4\}$, with adjacency defined by disjointness. The accompanying script enumerates all $2^{10}=1024$ vertex-deletion sets. For each one producing at least two components it computes $|S|/c(G-S)$ as an exact rational number. The minimum is \[ \tau(P)=\frac43. \] With the subsets in lexicographic order, the cut with indices $0,1,2,3$ attains the minimum and leaves three components. These indices correspond to the four subsets containing zero; the remaining six two-subsets of a four-element set form three disjoint edges.

The script independently proves non-Hamiltonicity of this particular finite graph by exhaustive path dynamic programming. A state $(S,v)$ records a simple path beginning at vertex zero, using exactly $S$, and ending at $v$. The initial state is $(\{0\},0)$; a state extends to every unused neighbour of $v$. By induction this records every simple path from zero. No state using all ten vertices ends at a neighbour of zero, so no Hamiltonian cycle exists. This supplies a finite certificate by complete enumeration, not a random search. Consequently a universal threshold, if one exists, must be strictly greater than $4/3$. No claim is made that this elementary obstruction is the strongest known lower bound.

Why the two extremal inequalities still fall short.

Toughness simultaneously controls every cut, whereas a proposed cycle must choose compatible entrances and exits through all relevant cuts. Even a bound on the independence number and a bound on connectivity do not reconstruct those choices. Conversely, attaching many isolated gadgets to a fixed separator makes Hamiltonicity fail but also makes the toughness small: if a separator of size $s$ exposes $r$ pieces, then toughness is at most $s/r$. Such a construction needs a proof that every separating set scales with the number of pieces before it can yield unbounded toughness.

Verification record and remaining gap.

The exact Petersen cut ratios and Hamiltonian-path calculation are in checks_graphs.py and results_graphs.json under _Local/Erdos_problems/UnsolvedMath/attempt_audit_2026_10_01/number_theory/. The argument excludes thresholds through $4/3$ and proves several necessary consequences of any larger threshold. It proves neither Hamiltonicity at a finite universal value nor unbounded toughness of non-Hamiltonian graphs. That uniform alternative is the remaining problem. Outcome: UNRESOLVED.

Sources

• S1 ULAM.AI, UnsolvedMath, supplied problems.json, record 1415 (GRAPH-028), statement and background. The embedded literature-review date is 2026-08-17; that is the archive’s review date, not a fresh certification. Dataset landing page: https://huggingface.co/datasets/ulamai/UnsolvedMath.

• S2 Hamiltonicity of 1-tough (P2 union kP1)-free graphs, Discrete Mathematics 348 $2025$. https://doi.org/10.1016/j.disc.2023.114082. Bibliographic information from the supplied record.

• S3 Hamiltonicity of 1-tough (P2 union kP1)-free graphs, arXiv:2303.09741. https://arxiv.org/abs/2303.09741. Bibliographic information from the supplied record.

• E1 Hamiltonicity of $1$-tough $(P_2\cup kP_1)$-free graphs, arXiv:2303.09741. https://arxiv.org/abs/2303.09741. Primary manuscript record inspected 1 October 2026. Its forbidden-induced-subgraph hypothesis is not part of the unrestricted toughness conjecture.