A graph with infinitely many distinct cycles

Question

I am trying to show the following statement, but I can't.

If a graph contains infinitely many distinct cycles then it contains infinitely many edge-disjoint cycles.

Answer 1

SKETCH: Let $\mathscr{C}$ be a maximal family of pairwise edge-disjoint cycles in $G$. If $\mathscr{C}$ is infinite, there’s nothing to prove, so assume that $\mathscr{C}$ is finite. By the pigeonhole principle there must be a $C_0\in\mathscr{C}$ that shares at least one edge with infinitely many cycles of $G$. Let $E$ be the set of edges of $C_0$; there must be some non-empty $S_0\subseteq E$ such that infinitely many cycles of $G$ share exactly the edges in $S_0$ with $C$. Call this set of cycles $\mathscr{C}_0$. Combine the cycles in $\mathscr{C}_0$ in pairs to get infinitely many pairwise edge-disjoint cycles.

It may help to think of the cycles in $\mathscr{C}_0$ as being like the edges of the pages in a book, with $S_0$ being the common edge along the spine of the book.

Added: That idea by itself isn’t quite enough, because some of the cycles in $\mathscr{C}_0$ may share edges other than those in $S_0$. Repeat the argument: if there is an infinite $\mathscr{C}_0'\subseteq\mathscr{C}_0$ that are edge disjoint except for the edges in $S_0$, the original idea works. Otherwise we can argue as before to find a $C_1\in\mathscr{C}_0$ and a subset $S_1$ of the edges of $C_1$ such that if $\mathscr{C}_1$ is the set of cycles in $\mathscr{C}_0$ that share exactly these edges with $C_1$, then $\mathscr{C}_1$ is infinite. Note that $S_0\subsetneqq S_1$. As before, if there is an infinite $\mathscr{C}_1'\subseteq\mathscr{C}_1$ that is edge disjoint except for the edges in $S_1$, we can use the original idea, and otherwise we repeat the argument. If we don’t get our infinite family of pairwise edge disjoint cycles in a finite number of steps, we will have found cycles $C_n$ and sets of edges $S_n$ for $n\in\Bbb N$ such that $S_n$ is a subset of the edges of $C_n$, $S_0\subsetneqq S_1\subsetneqq S_2\subsetneqq\ldots\;$, and whenever $m,n\in\Bbb N$ with $m<n$, the edges that $C_m$ shares with $C_n$ are precisely the edges in $S_m$. Here’s a rough schematic:

   __________________________________________________  
  |   0   |   1   |   2   |   3   |       |       |    
 0|       |A      |B      |C      |D      |       |  ···  
  |_______|_______|_______|_______|_______|_______|__   
      0       1       2       3  

The parts marked $0$ are the edges in $S_0$; $S_1$ corresponds to the parts marked $0$ and $1$; $S_2$ corresponds to the parts marked $0,1$, and $2$; and so on. $C_0$ includes the edges in $S_0$ and those schematically represented by A; $C_1$ includes the edges in $S_0$ and $S_1$ and those schematically represented by B; $C_2$ includes the edges in $S_0,S_1$, and $S_2$ and those schematically represented by C; and so on. The schematic should suggest how to build an infinite family of pairwise edge disjoint cycles in $G$ if this situation arises.