A connected graph 
is said to be 
-tough
if, for every integer 
,
cannot be split into 
different connected components by the removal of fewer than
vertices. 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 graph is complete iff 
(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's graph | 5/4 |
(1,2)-Blanusa snark, various  -hypohamiltonian
graphs | 9/7 |
Petersen
graph  | 4/3 |
