Graph toughness

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.

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.

He conjectured that the connection between toughness and Hamiltonicity goes in both directions: that there exists a threshold t such that every t-tough graph is Hamiltonian.

Chvátal's original conjecture that t = 2 would have proven Fleischner's theorem but was disproved by Bauer, Broersma & Veldman (2000).

The same is true for any fixed positive rational number q: testing whether a graph is q-tough is co-NP-complete (Bauer, Hakimi & Schmeichel 1990).

In this graph, removing the four red vertices would produce four connected components (depicted in four different colours). However, there is no set of k vertices whose removal leaves more than k components. Therefore, its toughness is exactly 1.