Results 1 to 6 of 6

Math Help - proof with graphs

  1. #1
    Junior Member
    Joined
    Feb 2011
    Posts
    38

    proof with graphs

    The graph G contains at least two vertices. One vertex has degree one, and every other vertex has degree greater than 1. Show that G contains a cycle.

    I was able to see that it was the case by drawing, but I need help getting started with the proof.
    I tried to make a connection with the theorem that says any walk starting with an odd degree must end in another odd degree vertex, but failed.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: proof with graphs

    If G does not have a cycle, then it is a tree, and in a tree, |V| = |E| + 1 where V is the set of vertices and E is the set of edges. Used together with the handshaking lemma and with the assumption about the degrees, this leads to a contradiction.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Feb 2011
    Posts
    38

    Re: proof with graphs

    So |V|=|E|+1 \\ \Rightarrow 2|E|=|E|+1 \\ \Rightarrow |E|=1
    and this is a contradiction because we assumed G has more than two vertices?
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: proof with graphs

    No, it does not follow from anywhere that 2|E| = |V| (this fact, I assume, is used in going from the first to the second line). Rather, the handshaking lemma says that \sum_{v\in V} \mathop{\text{deg}}(v)=2|E|. Since |E| = |V| - 1, we have \sum_{v\in V} \mathop{\text{deg}}(v) =2(|V|-1). Now find a lower bound for the left-hand side and compare it with the right-hand side.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Junior Member
    Joined
    Feb 2011
    Posts
    38

    Re: proof with graphs

    From the assumption about the degrees, \sum_{v\in V} \mathop{\text{deg}}(v) \ge 1+2(|V|-1).
    But then \sum_{v\in V} \mathop{\text{deg}}(v) =2(|V|-1) \ge 1+2(|V|-1) which is impossible?
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,545
    Thanks
    780

    Re: proof with graphs

    That's correct.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Help with proof on bipartite graphs!
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: November 14th 2010, 06:00 PM
  2. proof for bipartite graphs
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: March 29th 2010, 08:29 AM
  3. Replies: 0
    Last Post: December 29th 2009, 08:08 PM
  4. Proof and graphs
    Posted in the Discrete Math Forum
    Replies: 2
    Last Post: May 18th 2009, 08:24 AM
  5. Graphs
    Posted in the Pre-Calculus Forum
    Replies: 8
    Last Post: December 10th 2007, 10:13 AM

Search Tags


/mathhelpforum @mathhelpforum