A connected graph G is said to be t-tough if, for every integer k>1, G cannot be split into k different connected components by the removal of fewer than t k vertices. The toughness t(G) of a graph G is then defined as the largest real number such that deletion of any s vertices from G results in a graph which is either connected or else has at most s/t components. Toughness can be also be simply defined as t(G) = min_S ( left bracketing bar S right bracketing bar )/(c(G - S)) where c is the number of connected components and the minimum is taken over all vertex cuts S of G.

graph strength | vertex cut