Question

Prove that every tree has at least two vertices of degree 1

Answer 1

A tree must be connected by definition. This means that there can be no vertices of degree 0 in a tree. Assume for contradiction that we have v vertices and that v - 1 have degree at least degree two. Then we know that the sum of the degrees of the vertices is at least 1 + 2(v-1) which is equal to 2v - 1. Therefore we know that the number of edges must be at least v- 1/2 . But this is impossible because a tree must have exactly v - 1 edges. Thus we have shown by contradiction that every tree has at least two vertices.