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.

Printable View

- Apr 2nd 2010, 09:48 PMmyenemygraph 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. - Apr 4th 2010, 06:38 PMwgunther
Suppose G has no cycles of even length. Let $\displaystyle 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 $\displaystyle h_i E_H h_{i+1}$ and $\displaystyle h_n E_H h_1$. Then there is some i, j (wlog i<j) such that $\displaystyle h_i E_G h_j$ but $\displaystyle \neg(h_i E_H h_j)$.

Consider the two cycles

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

and

$\displaystyle 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. - Apr 5th 2010, 08:04 AMmyenemy
thanks for the reply wgunther, im kind of new to the world of graph theory, what do you mean by wlog?? and http://www.mathhelpforum.com/math-he...7143ba31-1.gif

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. - Apr 5th 2010, 08:34 AMwgunther
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