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 and
the minimum is taken over all vertex cuts 
of 
(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 
-tough graph is also 
-vertex-connected.
A complete graph has 
, and a graph with 
is complete
(Chvátal 1973).
While Chvátal (1973) defines 
for disconnected graphs,
using the definition of vertex cuts as cuts that increase
the number of connected components, the definition
can be applied to give well-defined toughnesses for disconnected
graphs.
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 
is 
,
and the toughness of a rook graph 
is 
.
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 |
