Toughness and Vertex Degrees
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 , but then show that for any integer , a best monotone theorem for requires at least nonredundant conditions, where grows superpolynomially as . When , we give an additional, simple theorem for G to be t-tough, in terms of its vertex degrees.
toughness best monotone theorem degree sequences