1. Not finding help here? Sign up for a free 30min tutor trial with Chegg Tutors
    Dismiss Notice
Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

A tree with at least 2 vertices has at least 2 leaves

  1. Oct 30, 2013 #1
    1. The problem statement, all variables and given/known data
    Prove by induction:
    A tree with n≥2 vertices has at least two leaves.

    2. Relevant equations
    A tree is a graph in which any vertices are connected by exactly 1 simple path, connected and has no cycles.

    A leaf is a vertex with degree = 1.


    3. The attempt at a solution

    I have to prove by induction, so I used the following steps so far:

    Base case: Let n = 2 vertices, then the vertices can be labeled as v1 and v2, and there is exactly 1 edge connecting the two vertices. Since there is only 1 edge, both v1 and v2 have degree 1, therefore v1 and v2 are leaves.

    Inductive hypothesis: Lets assume that for any tree with n = k vertices that the statement holds, that is, the tree has at least 2 leaves.

    Inductive step: This is where I was having trouble thinking of a solution that works? I was thinking that maybe I could do something like, every vertex with degree 2 can be deleted, thus the two vertices connecting to it will now be connected, and this can be followed until the tree is down to only leaves and vertices of degree > 2. but I didn't think that made much sense.

    Or something along the lines of there must be at least 2 vertices with only 1 path leading to the next vertex? I'm kind of stuck at this point.
     
  2. jcsd
  3. Oct 30, 2013 #2

    haruspex

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member
    2016 Award

    Suppose you first show there is at least one leaf. Can you see a different inductive step from there?
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted