Representative System for Graph Cycles Let $G$ be a graph containing precisely $n$ copies of $C_r$, where $n\geq 1$, $r\geq 3$, and no other cycles.
Under what conditions on $n, r$ does there exist a subgraph $H\subseteq G$ that shares precisely one edge each with every cycle of $G$?
 A: I claim $H$ always exists if and only if $r$ is odd or $n \leq 2$.
To see this, first assume $n \geq 3$ and $r$ is even. Note that $r \geq 4$. Then take two vertices $v$ and $u$ and three edge disjoint paths of length $\frac{r}{2}$ between them. This gives $3$ cycles of length $r$, and no matter how we choose two edges, there is always one cycle containing both of them. Hence $H$ does not exist.
Now assume $n \leq 2$ or $r$ is odd. We show $H$ exists.
If any two cycles are edge-disjoint, we can pick one edge from each arbitrarily and we are done.
So assume there are two cycles $C_1$ and $C_2$ which share at least one edge. Pick a vertex $v$ on $C_1$ of degree at least $3$ in $G[C_1 \cup C_2]$, and take a path $P$ from $v$ to $C_1$, edge-disjoint from $C_1$ (essentially, we walk from $v$ on $C_2$ until we hit $C_1$ again). Let $u$ be the endpoint of $v$. Then we have three edge-disjoint paths from $v$ to $u$. As all cycles of $G$ have the same length $r$, all paths must have the same length $\frac{r}{2}$, and also $n \geq 3$. This is a contradiction, proving the claim.
In fact, it is possible to characterize all graphs having a single cycle length. They are graphs where each $2$-connected component is a cycle, if $r$ is odd, or a collection of edge-disjoint paths of length $\frac{r}{2}$ between two vertices.
