What is "graph toughness"

n. (mathematics) a measure, expressed by a positive integer (with the exception of complete graphs) of the connectivity of a graph

In graph theory, toughness is a measure of the connectivity of a graph. A graph is said to be -tough for a given real number if, for every integer , cannot be split into different connected components by the removal of fewer than vertices. For instance, a graph is -tough if the number of components formed by removing a set of vertices is always at most as large as the number of removed vertices. The toughness of a graph is the maximum for which it is -tough; this is a finite number for all graphs except the complete graphs, which by convention have infinite toughness.

Graph toughness was first introduced by . Since then there has been extensive work by other mathematicians on toughness; the recent survey by lists 99 theorems and 162 papers on the subject.