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?
Best Answer
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.