A graph with independence number $\alpha(G)$ decomposes into at most $\alpha(G)$ cycles, edges or isolated vertices

Question

Currently I'm struggling with the following problem, which I find quite interesting:

Given a graph $G$, let $\alpha(G)$ denote the largest size of a set of independent vertices in $G$. Prove that the vertices of G can be covered by at most $\alpha(G)$ disjoint subgraphs each isomorphic to a cycle or a $K_2$ or $K_1$.

I think it's interesting, because it applies to any graph and gives you a decomposition into potentially very few cycles if the independence number is small. It tried a few things and this is what I found out so far:

• We may assume that $G$ is connected since the independence number of $G$ equals the sum of the independence numbers of its connected components

• We can also assume that $G$ has no isolated vertices, because these will definitely be included in any maximal independent set

• Lastly I think that we can also assume that $G$ has no vertices of degree $1$ i.e. leafs, because taking a leaf and it's unique neighbour yields a $K_2$ and if we delete this $K_2$ the independence number of the graph drops by exactly $1$, because any maximal independent set will intersect either one of the vertices in this $K_2$

Putting these assumptions together we may assume that $G$ is a connected graph with minimum degree $\ge 2$. The arguments I made already show that any forest can be decomposed as described (with no cycles of course). Now I am stuck and don't know how to continue anymore, I feel like I need a completely different argument to continue. Maybe someone has an idea how to proceed?

I would be grateful for any new suggestions :)

EDIT: The subgraphs don't have to be induced subgraphs isomorphic to $K_1,K_2$ or a cycle. So any hamiltonian graph would work instantly, because we could just take the Hamiltonian cycle.

Answer 1

Fair warning for the post below: I am very drowsy and the arguments within are to be read skeptically.

(Just for context, this question is from Diestel's Graph Theory right? The chapter on matching, packing and covering)

We'll prove this recursively, by showing that we can repeatedly find (and then remove) some cycle / $K_2$ / $K_1$ that contains the entire closed neighborhood of some vertex. For a vertex $v$, let $N[v]$ denote the closed neighborhood of $v$ (i.e., the set with $v$ and all the vertices it is adjacent to).

Lemma. Let $G$ be a graph and $u$ any vertex of $G$. Then $\alpha(G - N[u]) \leq \alpha(G) - 1$.

Proof of Lemma: Let $I$ be a maximum-cardinality independent set of $G - N[u]$. The set $I \cup \{u\}$ is an independent set of $G$ with $\alpha(G - N[u]) + 1$ vertices. Therefore $\alpha(G) \geq \alpha(G - N[u]) + 1$.

Proposition: $G$ can be covered by a collection of $\alpha(G)$ graphs, all of which are either a cycle, or $K_2$, or $K_1$.

Proof of Proposition: We proceed by induction on $\alpha$. If $\alpha(G) = 1$, then $G$ is a complete graph, and is thus either $K_1$, $K_2$, or covered by a cycle containing all its vertices.

Now suppose the proposition is true for all graphs $H$ with $\alpha(H) \leq k$, and let $G$ be a graph with $\alpha(G) = k + 1$. The Proposition follows immediately if $G$ has maximum degree 1, so we can assume $\Delta(G) \geq 2$. Let $P = u_0, u_1, \dots, u_j$ be a path of maximum length in $G$ ($P$ is not necessarily induced!) Note that every neighbor of $u_j$ lies in $P$: for if $u_j$ had a neighbor $v$ that was not in $P$, then $P\cup \{v\}$ would be a longer path. Let $u_i$ be the first vertex of $N[u_j] \cap P$. If $u_i = u_{j-1}$ (so $u_j$ has only one neighbor), then let $C$ be the copy of $K_2$ induced by $u_i$ and $u_j$. Otherwise, let $C$ be the cycle $C = P[u_i,u_j]\cup \{u_iu_j\}$ (so $C$ follows $P$ from the first neighbor of $u_j$, to $u_j$, then follows the edge $u_ju_i$ to finish the cycle). In either case, $C$ contains all of $N[u_j]$. Therefore, by our Lemma, $\alpha(G-C) \leq k$. By the induction hypothesis, we get our cover by cycles, $K_2$ copies and $K_1$ copies by taking such a cover of $G-C$, and adding the cycle $C$ to it.