# Graph Theory question about trees

• November 26th 2009, 04:30 PM
Beastie
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.
• November 27th 2009, 03:52 AM
emakarov
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?