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

and

A moment shows (and drawing a picture will help) that one of these has even length. Contradiction.