A necessary and sufficient condition for the existence of a path factor every component of which is a path of length at least two

A P-greater than or equal to3-factor F of a graph G is a spanning subgraph of G such that every component of F is a path of length at least two. Let R be a factor-critical graph with at least three vertices, that is, for each x is an element of V(R), R - x has a 1-factor (i.e., a perfect matching). Set V(R) = {x(1),..., x(n)}. Add new vertices {v(l),...,v(n)} to R together with the edges x(i)v(i), 1 less than or equal to i less than or equal to n . The resulting graph H is called a sun. (Note that deg(H) v(i) = 1 for all i, 1 less than or equal to i less than or equal to n.) K-1 and K-2, i.e., the complete graphs with one and two vertices, respectively, are also called suns. Then let W be the set of all suns. A sun component of a graph is a component which belongs to W. Let c,(G) denote the number of sun components of G. We prove that a graph G has a P-greater than or equal to3-factor if and only if c(s)(G - S) less than or equal to 2\S\, for every subset S of V(G). (C) 2003 Elsevier Science (USA). All rights reserved.