# Is the minimum length cycle basis necessarily made up of induced cycles?

I am using the definitions given in this Wikipedia article. I am considering unweighted graphs or equivalently graphs where all edges have the same weight, say equal to 1.

I am interested in bases of the cycle space that minimize the total length (I write length rather than weight because I am considering unweighted graphs as remarked above). As explained in the Wikipedia article, such a basis of the cycle space must necessarily be a cycle basis, i.e. all its elements must be simple cycles.

Now, the article further states that

Every graph has a cycle basis in which every cycle is an induced cycle.

I am wondering: Is the minimal length cycle basis necessarily such a cycle basis consisting only of induced cycles?

Yes, a cycle basis of minimum total length is necessarily made up of induced cycles.

Let $$\mathcal C_1,\mathcal C_2,\cdots, \mathcal C_r$$ be a cycle basis of minimum total length, where $$r\ge1$$.

For the sake of contradiction, suppose $$\mathcal C_1=(v_1,v_2,\cdots,v_q)$$ where $$v_1=v_q$$ is not an induced cycle. That means $$q\ge4$$ and there is a "chord" $$(v_a, v_b)$$ across $$\mathcal C_1$$, i.e., $$(v_a,v_b)$$ is an edge of the original graph where $$a,b$$ are not adjacent integers nor $$\{1, q-1\}$$. WLOG, let the chord be $$(v_1, v_p)$$, where $$v_p$$ is not one of $$v_1, v_2, v_{q-1}$$. We have $$2\lt p\lt q-1$$.

Consider cycle $$\mathcal D=(v_1,v_2 \cdots, v_p, v_1)$$ and cycle $$\mathcal E=(v_1, v_p, v_{p+1}, \cdots, v_q)$$. Either $$\mathcal D$$ or $$\mathcal E$$ is not a $$\mathbb Z_2$$-combination of $$\mathcal C_2, \cdots, \mathcal C_r$$; otherwise, $$\mathcal D + \mathcal E=\mathcal C_1$$ is also a $$\mathbb Z_2$$-combination of them, which implies $$\mathcal C_1,\mathcal C_2,\cdots, \mathcal C_r$$ is not a cycle basis, which contradicts with our assumption.

WLOG, suppose $$\mathcal D$$ is not a $$\mathbb Z_2$$-combination of $$\mathcal C_2, \cdots, \mathcal C_r$$. That means $$\mathcal D, \mathcal C_2, \cdots, \mathcal C_r$$ are $$\mathbb Z_2$$-linearly independent. Hence $$\mathcal D, \mathcal C_2, \cdots, \mathcal C_r$$ is a cycle basis. However, its total length is less than that of $$\mathcal C_1,\mathcal C_2,\cdots, \mathcal C_r$$ since the length of $$\mathcal D$$ , $$p$$ is less than the length of $$\mathcal C_1$$, $$q$$. This is a contradiction.

• Nicely explained. Thank you very much. Aug 16, 2022 at 10:01