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

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.

• Does something like this work? Let $v$ be a vertex in the maximum independent set and find a cycle starting and ending at $v$. If it's not possible, find a $K_2$. If still not possible, find a $K_1$. Either way, we have found a graph $H \subseteq G$ with $v \in V(H)$. Then notice that $\alpha(G - H) \leq \alpha(G) - 1$ and induct our way down? (Independence number usually doesn't decrease when taking subgraphs, but in this case it does because the subgraph is induced.) Commented Aug 7 at 1:47
• Thank you, I will try to do this! @koifish Commented Aug 7 at 6:33
• I'm not super comfortable with this proof also, because it means that I can replace "cycle" with any graph $H$ such that the induction base case will go through. For example, I can replace "cycle" with "complete graphs", and the induction will go through, since when $\alpha(G) = 1$, I can cover $G$ with a single complete graph. Commented Aug 7 at 9:58
• Yes, I agree it still is not clear to me how/why we have induced cycles in the decomposition. I also struggle to understand how the independence number behaves, when splitting the graph into disjoint induced subgraphs. @koifish Commented Aug 7 at 10:12
• The vertices of $H$ make up the cycle, for each time you remove $H$. Does that work? Commented Aug 7 at 11:08

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.

• Oh my, thank you very much, this problem bugged me for days. You're right this problem is from Diesel, I am trying to do the exercises for practice. It says that I can not award the bounty yet, but you will get it for sure. Commented Aug 9 at 8:21
• I had the same experience first time I tried it - couldn't solve it, and couldn't ignore it either! Commented Aug 9 at 8:39