Toughness and the Existence of k-Factors. II
Combinatorics Springer-Verlag · 1986
In a paper with the same title (3), we proved ChvMal's conjecture that k-tough graphs have k-factors if they satisfy trivial necessary conditions. In this paper, we prove the following stronger result: Suppose (V(G)I _> k + 1, k. IV(G)( even, and JSI > k'w(G - S)--Tk if w{G - 5') _ 2, where w(G - S) is the number of connected components ofG - S. Then G has a k-factor. We consider finite undirected graphs without loops and multiple edges. We denote by V(G) and E(G) the set of vertices and the set of edges of a graph G, respectively. For subsets S and T of V(G), e e (S, T) is the number of edges joining S and T. A vertex x is often identified with {x}. For example, ee(x, T) means es({x}, T). More- over, a subset S of V(G) is often identified with the subgraph induced by S. The subgraph induced by V(G) - S is denoted by G - S. The set of vertices adjacent to x in G is denoted by Fe(x), and de(x ) := (Fe(x)( is the degree ofx in G (A := B means that A is defined by B). For a subset S of V(G), Fe(S) := Vx~sFe(x). We denote by w(G) the number of connected components of G. A k-regular spanning subgraph is called a k-factor. We use the following criterion for a graph to have a k-factor: For disjoint subsets A and B of V(G), 6e(A,B):=k'IAJ+ Z de-a(x) - k'(BI - he(A,B ), x~B