- #1
Jcampuzano2
- 5
- 0
Homework Statement
Prove by induction:
A tree with n≥2 vertices has at least two leaves.
Homework 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.
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: Let's 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.