Results 1 to 4 of 4

Math Help - graph theory proof

  1. #1
    Newbie
    Joined
    Apr 2010
    Posts
    13

    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.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Newbie
    Joined
    Jan 2008
    Posts
    19
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Apr 2010
    Posts
    13
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Newbie
    Joined
    Jan 2008
    Posts
    19
    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
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Graph Theory Proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: April 4th 2011, 01:16 AM
  2. graph theory proof
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: May 20th 2010, 03:27 AM
  3. graph theory proof
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: May 12th 2010, 12:00 AM
  4. Graph theory: proof
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: October 29th 2009, 01:00 PM
  5. Graph Theory Proof please:-
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: October 18th 2008, 04:06 PM

Search Tags


/mathhelpforum @mathhelpforum