![cover image](https://wikiwandv2-19431.kxcdn.com/_next/image?url=https://upload.wikimedia.org/wikipedia/commons/thumb/5/5b/Graph_toughness.svg/640px-Graph_toughness.svg.png&w=640&q=50)
Graph toughness
From Wikipedia, the free encyclopedia
In graph theory, toughness is a measure of the connectivity of a graph. A graph G is said to be t-tough for a given real number t if, for every integer k > 1, G cannot be split into k different connected components by the removal of fewer than tk vertices. For instance, a graph is 1-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 t for which it is t-tough; this is a finite number for all finite graphs except the complete graphs, which by convention have infinite toughness.
![Thumb image](http://upload.wikimedia.org/wikipedia/commons/thumb/5/5b/Graph_toughness.svg/240px-Graph_toughness.svg.png)
Graph toughness was first introduced by Václav Chvátal (1973). Since then there has been extensive work by other mathematicians on toughness; the recent survey by Bauer, Broersma & Schmeichel (2006) lists 99 theorems and 162 papers on the subject.