Toughness and the existence of <i>k</i>‐factors

Abstract

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) &gt; 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.