Let G be a simple graph. Suppose that size of largest independent set in G is α. Prove that:
a) Vertices of G can be partitioned to at most α paths.
b) Suppose that a vertex and an edge are also cycles. Prove that vertices of G can be partitioned to at most α cycles. combinatorics proposedcombinatorics