I tried using the contrapositive to prove the original statement:
If no cycle in G is an induced subgraph, then G is a graph with no odd cycles.
To prove this, I assumed that G did have an odd cycle that was not an induced subgraph. However, if the odd cycle is not an induced subgraph, then there is an edge connecting two vertices in the "cycle" that shortens the cycle, in a sense, by bypassing some vertices and edges, which creates a new cycle. If this cycle is even, then there is a contradiction, since G was assumed to have no even cycles. If this cycle is odd, then there is a contradiction, since it is an induced subgraph of G.
Am I thinking about this in the right way?
Best Answer
To add to the comment above, your contrapositive hypothesis is also not correct. The correct contrapositive statement is:
"If there exists a cycle in $G$ that does not yield an induced subgraph, then $G$ has an even cycle."
Now the contrapositive approach in itself seems fine. Consider such a cycle $C$; if the cycle has an even number of vertices, we're done. So suppose it has an odd number of vertices. Then the fact that it does not yield an induced subgraph means that there exists an additional edge between two of the vertices in $C$. Can you see why the addition of such an edge must mandate the creation of an even cycle?