Suppose G has no cycles of even length. Let be a cycle of G (of odd length) and suppose it is not an induced subgraph of G (assume wlog that and . Then there is some i, j (wlog i<j) such that but .
Consider the two cycles
A moment shows (and drawing a picture will help) that one of these has even length. Contradiction.