Star-Cycle Factors of Graphs

A spanning subgraph $F$ of a graph $G$ is called a star-cycle factor of $G$ if each component of $F$ is a star or cycle. Let $G$ be a graph and $f : V (G) → {1, 2, 3, . . .}$ be a function. Let $W = {v ∈ V (G) : f(v) = 1}$. Under this notation, it was proved by Berge and Las Vergnas that G has a star-cycle factor $F$ with the property that (i) if a component $D$ of $F$ is a star with center $v$, then $deg_F (v) ≤ f(v)$, and (ii) if a component $D$ of $F$ is a cycle, then $V (D) ⊆ W$ if and only if $iso(G − S) ≤ Σ_{x∈S} f(x)$ for all $S ⊂ V (G)$, where $iso(G − S)$ denotes the number of isolated vertices of $G − S$. They proved this result by using circulation theory of flows and fractional factors of graphs. In this paper, we give an elementary and short proof of this theorem.