I just received an assignment back and was told that my proof to the following was not valid; I'm not sure why. Would appreciate if someone could point out my errors.
Prove that if G is a graph with no cycles of even length, then every cycle in G is an induced subgraph of G.
Note that every induced subgraph of G is obtained by deleting a subset of vertices from G. Let U denote such a subset of vertices. Let C denote a cycle of G.
We will show that C does not share two or more common vertices with any other cycle D of G. Suppose otherwise. Then there exists at least two vertices in C that form a cycle with vertices from D. Let C' denote the induced subgraph with the common vertices of C and D, and denote . Let D' denote the induced subgraph with vertices from D not in C, so . If |D'| is odd, then there exists an even cycle with and and , contradicting the assumption that there exist no cycles. If |D'| is even, then there exists an even cycle with and , again contradicting our assumption.
So every vertex of C lies only on C. It follows that we can remove any vertex set incident with the vertices of C. If we remove all such vertex sets, we obtain C. So every cycle in G is an induced subgraph of G.