# Thread: graph theory proof

1. ## graph theory proof

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.

2. Suppose G has no cycles of even length. Let $H=\{ h_1,h_2,\ldots,h_n\}$ be a cycle of G (of odd length) and suppose it is not an induced subgraph of G (assume wlog that $h_i E_H h_{i+1}$ and $h_n E_H h_1$. Then there is some i, j (wlog i<j) such that $h_i E_G h_j$ but $\neg(h_i E_H h_j)$.

Consider the two cycles

$h_1\rightarrow \cdots\rightarrow h_i\rightarrow h_j\rightarrow h_{j+1}\rightarrow \cdots \rightarrow h_n\rightarrow h_1$

and

$h_i\rightarrow h_{i+1}\rightarrow \cdots\rightarrow h_{j-1}\rightarrow h_j\rightarrow h_i$

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

3. thanks for the reply wgunther, im kind of new to the world of graph theory, what do you mean by wlog?? and

i can see quite clearly that this statement is obviously true and can show it with a diagram but how to show proof of it in mathematical terms is where i get abit lost.

4. 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