# A graph theory problem about covering

Given a simple graph $G$, let $\alpha (G)$ be the maximal order of the independent vertices of $G$. Show that the vertices of $G$ can be covered by at most $\alpha (G)$ nonintersected subgraphs, each of which is isomorphic to a cycle or $K_2$ or $K_1$.

Induction may help?

Induction seems like a good idea, the obvious thing we'd like to do is take some cycle $C$, look at $G-C$ and see if $\alpha(G-C)<\alpha(G)$, if so we are done.
Otherwise every vertex of $C$ has some neighbour outside of $C$, but by considering a longest path in $G$, of which the end vertex $v$ then has all its neighbours on the path which we can then close up to make a cycle (or a $K_1$ or $K_2$ in some trivial cases) where $v$ has all its neighbours on the cycle.