Prove that if G is a graph with no cycles of even length, then every cycle in G is an induced subgraph of G.
any help would be great
thanks.
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.
Wlog means without loss of generality. When I say E sub H I mean the edge relation on the graph H. It's pretty simple to prove from here. Count the number of vertices in each. One has n+j-i and the other is i-j. They sum to n. n is odd, thus one of the two is even