The graph need not be composed solely of a cycle, but every cycle in the graph need be an odd length cycle. I tried a contrapositive proof, trying to prove that if all vertices have degree greater than or equal to 3 then a graph does not contain any odd cycles but I didn't get very far with that.
Graph Theory – Prove Vertex Degree Less Than 3 in Graphs with Only Odd Cycles
discrete mathematicsgraph theory
Best Answer
Suppose that $G$ has only cycles of odd length as well as no vertex with degree less than 3. Clearly we may assume that $G$ has one connected component.
Let $C$ be a cycle and with some edge $e$ from $c$ to $d$ in $C$.
Claim: $e$ does not lie in any other cycle $C'$. First, if $C'$ only meets $C$ at the vertices $c$ and $d$ then we can form a larger cycle by going from $c$ to $d$ in $C$ and then from $d$ to $c$ in $C'$, which has $\# C - 1 + \#C' - 1$ edges, which is even since those two cycles are odd, and that is a contradiction. So they meet in at least one point. Let $f$ be the first point in $C$ we reach by following $C'$. This allows us to obtain two new cycles: follow $c$ to $f$ in $C'$ then $f$ to $c$ in $C$, as well as $c$ to $f$ in $C'$ then $f$ to $c$ in $C$. One of these two must have even length because between them they have $\#C + 2$ edges, which is an odd number, and the only way to get an odd integer as a sum is when at least one of the two integers is odd (in fact exactly one). So again we have a contradiction.
So the graph can be decomposed into the collection of all the cycles in $G$, and these cycles meet each other in at most one vertex. You can see how this gives rise to a new graph $H$ by collapsing all the cycles to points. That graph must be a tree, because any cycle in it clearly descends to a new cycle in $G$, yet all of the cycles in $G$ are represented already. Moreover, the leaves of $H$ must consist of these collapsed cycles or else they would correspond to an actual leaf in $G$, a vertex of degree $1<3$.
Take a cycle $C$ in $G$ corresponding to a leaf of the tree $H$. So exactly one vertex of $C$ also lies on another cycle, but neither of the other vertices do (of which there are at least 2). Then neither of the other vertices can have any other edges, and in particular they have degree 2, yet every vertex in $G$ was supposed to have degree at least 3, which is our final contradiction.