2What is the sum of the degrees of vertices of a tree with n

2.What is the sum of the degrees of vertices of a tree with n vertices?

3.Prove that a tree with at least two vertices has at least two vertices of degree 1. (Hint: Use the answer to Question 2.)

Notice that any tree must have at least one vertex with degree 1

because if every vertex had degree of at least 2, then one would always be

able to continue any walk until a cycle is formed. Now let us assume that we

have a tree with exactly one vertex of degree 1. If one removes this vertex

of degree 1, the resulting graph must also be a tree since a cycle cannot be

added by removing a vertex. In the resulting tree, either the first vertex’s

neighbor is now of degree 1 or the resulting graph is not a tree and we have

a contradiction. If the latter, our proof is done. If the former, we must be

able to remove vertices until a contradiction occurs, and there is no vertex of

degree 1. We must be able to do this because if we could continue to remove

vertices in this way, our graph must be something equivalent to a straight

path, and a straight path has two vertices of degree 1, namely the endpoints.

We have shown that a tree must have at least one vertex of degree 1 and

that it cannot have exactly one, so it must have at least two.

(or)