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

AbstractA P⩾3-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∈V(R),R−x has a 1-factor (i.e., a perfect matching). Set V(R)={x1,…,xn}. Add new vertices {v1,…,vn} to R together with the edges xivi,1⩽i⩽n. The resulting graph H is called a sun. (Note that degHvi=1 for all i,1⩽i⩽n.) K1 and K2, i.e., the complete graphs with one and two vertices, respectively, are also called suns. Then let C be the set of all suns. A sun component of a graph is a component which belongs to C. Let cs(G) denote the number of sun components of G. We prove that a graph G has a P⩾3-factor if and only if cs(G−S)⩽2|S|, for every subset S of V(G)