0
$\begingroup$

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?

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.