We prove the following conjecture of A. Frank (Fifth British Combinatorial Conference, Aberdeen, Scotland, 1975): Let G be a connected simple graph of order n, and n=n(1)+...+n(k) be a partition of n with n(i) greater than or equal to 2. Suppose that the minimum degree of G is at least k. Then the vertex set V(G) can be decomposed into disjoint subsets V-1,...,V-k so that /V-i/=n(i) and the subgraph induced by V-i contains no isolated vertices for all i, 1 less than or equal to i less than or equal to k. (C) 1995 Academic Press, Inc. [References: 4]
展开▼
