Toughness and the existence of k‐factors
Hikoe Enomoto, Bill Jackson, Panagiotis Katerinis, Akira Saito · Journal of Graph Theory · 1985
Abstract A connected graph G is called t‐tough if t · w(G ‐ S) ⩽ |S| for any subset S of V(G) with w(G ‐ S) > 1, where w(G ‐ S) is the number of connected components of G ‐ S. We prove that every k‐tough graph has a k‐factor if k|G| is even and |G| ⩾ k + 1. This result, first conjectured by Chvátal, is sharp in the following sense: For any positive integer k and for any positive real number ε, there exists a (k ‐ ε)‐tough graph G with k|G| even and |G| ⩾ k + 1 which has no k‐factor.