Prove that if a graph contains only odd cycles, there must exist a vertex with degree less than 3. 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. 
 A: 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.
A: A slightly stronger version: a nontrivial graph with no even cycles has at least two vertices of degree less than $3$. ("Nontrivial" means that the graph has more than one vertex.)
I will prove the contrapositive: if a nontrivial graph has at most one vertex of degree less than $3$, then it has an even cycle.
In fact, I will show that a nontrivial (finite simple) graph $G$ with at most one vertex of degree less than $3$ must contain a theta graph, i.e., a graph consisting of two distinct vertices connected by three internally disjoint (simple) paths. Then two of the three paths must have lengths of the same parity, thus forming an even cycle.
Let $P=(v_1,v_2,\dots,v_n)$ be a maximal path in $G$ with $n\gt1$. At least one endpoint of $P$ has degree at least $3$. We may assume that $v_1$ has degree at least $3$, so it has at least two neighbors besides $v_2$. Since $P$ is a maximal path, all neighbors of $v_1$ must lie on $P$; so $P$ has neighbors $v_2,v_i,v_j$ where $2\lt i\lt j\le n$. Now there are three internally disjoint paths from $v_1$ to $v_i$: the path $P_1=(v_1,v_i)$, the path $P_2=(v_1,v_2,v_3,\dots,v_{i-1},v_i)$, and the path $P_3=(v_1,v_j,v_{j-1},\dots,v_{i+1},v_i)$.
Remark. We can also show that, for any prime $p\gt2$, if a nontrivial graph has at most one vertex of degree less than $3$, then it has a cycle whose length is not divisible by p. As we have just shown, there are two vertices connected by three internally disjoint paths $P_1,P_2,P_3$, where the path $P_1$ has length $1$. If the cycles $P_1\cup P_2$ and $P_1\cup P_3$ both have lengths divisible by $p$, then the paths $P_2$ and $P_3$ have lengths congruent to $-1$ modulo $p$, and so the cycle $P_2\cup P_3$ has length congruent to $-2$ modulo $p$, and therefore not divisible by $p$.
A: We will prove the contrapositive statement. Specifically, if all vertices have degree greater than or equal to 3, then there must exist an even cycle.
Let $x$ be an endpoint of a maximal path. We know that $x$ has degree at least 3 so it is connected to at least three other vertices $u$, $v$, and $w$. We know that these three vertices must all lie on the maximal path. WLOG, let $w$ be vertex adjacent to $x$ in the maximal path.
If the path from $x$ to $v$ along the maximal path is of odd length, then we know that there is an even cycle. Specifically, the path from $x$ to $v$ along the maximal path plus the edge $(x, v)$ will form an even cycle. The same argument holds if the path from $x$ to $u$ along the maximal path is of odd length. So if the path from either $x$ to $v$ or $x$ to $u$ is of odd length, we have an even cycle.
Otherwise, it must be that the path from $x$ to $v$ and the path from $x$ to $u$ along the maximal path are both of even length. In this case, it must be that the path from $u$ to $v$ is also of even length. Adding in the edges $(u, x)$ and $(x, v)$, we have found a cycle of even length.
Thus, in all cases, if all vertices have degree greater than or equal to 3, there exists an even cycle.
