Results 1 to 2 of 2

Math Help - Graph Theory question about trees

  1. #1
    Newbie
    Joined
    Nov 2009
    Posts
    1

    Smile Graph Theory question about trees

    Ok so I am trying to prove by induction that If T is a tree with 3 or more vertices then T has a vertex that is not a leaf.

    I got my P(1) step, but I am getting strung up when I try to go for my
    p(n) => p(n+1) step.

    any help would be greatly appreciated.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,559
    Thanks
    785
    Consider cases of two and three vertices also as the base case. For bigger trees, if one has a non-leaf vertex v and adds another vertex and an edge, can v become a leaf?
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 2
    Last Post: March 2nd 2011, 06:39 AM
  2. Graph Theory - Trees and Paths
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 10th 2010, 12:14 AM
  3. [SOLVED] Graph Theory and Labeled Trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 9th 2009, 08:10 AM
  4. Graph theory: Trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: October 3rd 2009, 01:30 PM
  5. [SOLVED] Graph Theory - Trees
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: November 8th 2007, 01:29 AM

Search Tags


/mathhelpforum @mathhelpforum