Results 1 to 3 of 3

Math Help - Mathematical Induction

  1. #1
    Junior Member
    Joined
    May 2010
    Posts
    26

    Mathematical Induction

    Hi guys,

    Had this question today in my final but dont know how to complete, any suggestions would be appreciated.

    Using induction proof to show that every tree has one more node than it has edges.

    That is, to prove the statement:

    If
    T is a tree, and T has n nodes and e edges, then

    n = e + 1.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor Swlabr's Avatar
    Joined
    May 2009
    Posts
    1,176
    Quote Originally Posted by extatic View Post
    Hi guys,

    Had this question today in my final but dont know how to complete, any suggestions would be appreciated.

    Using induction proof to show that every tree has one more node than it has edges.

    That is, to prove the statement:

    If
    T is a tree, and T has n nodes and e edges, then

    n = e + 1.
    (I am presuming you are talking about connected trees...? A disconnected tree could have n nodes and zero edges...)

    Induct on the number of edges. If it has one edge it must have 2 nodes, one at each end of the edge.

    Assume true for all trees with r edges. Then the number of nodes is r+1 on such a tree.

    Let \Gamma be a tree with r+1 edges. Then it contains a subtree with r edges (just delete one of the bottom-most edges and the ONE node at its tip). This tree, \Gamma^{\prime}, has r+1 nodes, but as we deleted ONE node from \Gamma this means that \Gamma must have r+2 nodes.

    As e=r+1 we have that n=r+2 = (r+1)+1 = e+1 as required.

    Is there anything you specifically do not understand in this?...
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    May 2010
    Posts
    26
    Thankyou Swlabr, your response is awesome!
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. Replies: 10
    Last Post: June 29th 2010, 12:10 PM
  2. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: April 7th 2010, 12:22 PM
  3. Mathematical Induction
    Posted in the Algebra Forum
    Replies: 9
    Last Post: July 8th 2009, 12:27 AM
  4. Mathematical Induction
    Posted in the Number Theory Forum
    Replies: 4
    Last Post: February 17th 2009, 11:30 AM
  5. Mathematical Induction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: May 30th 2007, 03:21 PM

Search Tags


/mathhelpforum @mathhelpforum