We study theorems giving sufficient conditions on the vertex degrees of a graph G to guarantee G is t-tough. We first give a best monotone theorem when t is at least 1, but then show that for any integer k > 0, a best monotone theorem for t=1/k requires at least f(k)|V(G)| nonredundant conditions, where f(k) grows superpolynomially as k grows to infinity. When t < 1, we give an additional, simple theorem for G to be t-tough, in terms of its vertex degrees.
- Degree condition
- Best monotone theorem