# Prove that if G is a graph with no even cycles, then every cycle in G is an induced subgraph.

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.

• The negation of "no even cycle" is NOT "no odd cycles". – N. S. Mar 29 '15 at 1:09
• But doesn't "no even cycles mean" that "every cycle is odd", so negating that gives "every cycle is even" which is equivalent to saying "no cycles are odd"? @N.S. – user227157 Mar 29 '15 at 1:12
• The negation of "there is no even cycle" is "there is a even cycle", and it does not assert the existence of odd cycle. – Hanul Jeon Mar 29 '15 at 1:15
• @user227157, the problem is that you're assuming that the graph has cycles in the first place. – Machine Caliber Mar 29 '15 at 1:15
• The negation of "every cycle is odd" is "some cycles are even". – N. S. Mar 29 '15 at 1:16

"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?