Graph toughness measures resistance to separation by removal of vertices. A connected graph 
is 
-tough if, for every integer 
, 
cannot be split into 
different connected components
by the removal of fewer than 
vertices. The property of
being 
-tough
is also called 
-toughness.
The toughness 
of a graph 
is then defined as the largest real
number such that deletion of any 
vertices from 
results in a graph which is either
connected or else has at most 
components. Toughness
can be also be simply defined as
 |
where 
is the number of connected components. For
a complete graph, there is no such set 
, and the toughness is defined to be
(Chvátal 1973).
This property was termed "toughness" because it measures how tightly various pieces of a graph "hold together" (Chvátal
1973). In particular, every noncomplete 
-tough graph is also 
-vertex-connected.
A complete graph has 
, and a graph with 
is complete
(Chvátal 1973).
For a disconnected graph, the choice 
gives 
, as in Chvátal's (1973) definition.
An edge cut analog of toughness is known as graph strength.
Recognizing a graph as being 1-tough is NP-hard (Bauer et al. 1990).
Note that all (not just minimum vertex cuts) must be considered. For example, in the case of the 3-gear
graph, 
is a minimum vertex cut of size 2 whose removal
leaves two components giving a ratio 
, while removing the vertex
cut 
of size 3 leaves 4 components giving a ratio 3/4, which is the minimum possible.
Chvátal (1973) showed that the toughness of a complete bipartite graph 
with 
and 
is 
,
and the toughness of a rook graph 
with 
is 
. The excluded cases 
and rook graphs with a factor of size one are complete graphs, with infinite toughness.
Every Hamiltonian graph is 1-tough (i.e., has toughness 
),
but counterexamples exist, the smallest being
on 7 vertices, for which a nonhamiltonian
graph has toughness 1. Chvátal (1973) conjectured that all graphs
which are more than 3/2-tough are Hamiltonian,
but this was disproved by Bauer et al. (2000), who showed that not every 2-tough
graph is Hamiltonian.
Chvátal's toughness conjecture posits that
there exists a toughness threshold 
above which 
-tough graphs are always Hamiltonian;
its truth remains unresolved (Bauer et al. 2000).
Small nonhamiltonian graphs with toughness greater than 1 are summarized in the table below.
nonhamiltonian graph with toughness  |  |
| (1,1)-Blanusa snark | 8/7 |
various
 -hypohamiltonian
graphs | 7/6 |
Sousselier
graph, 16-Lindgren-Sousselier graph, various  -hypohamiltonian
graphs | 6/5 |
| (13,1)-hypohamiltonian graphs, Tietze graph | 5/4 |
(1,2)-Blanusa snark, various  -hypohamiltonian
graphs | 9/7 |
Petersen
graph  | 4/3 |
For every 
and integer 
, graphs of simplicial
polytopes of dimension 
and vertex connectivity
exactly 
can have arbitrarily small toughness and no Hamiltonian
path (Pineda-Villavicencio 2026).
