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

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

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

Solution

Answer :

1) A tree with n vertices must have n - 1 edges.

Since by Hand Shaking lemma in a graph the sum of the degrees of the vertices is equal to the twice the number of the edges.

So the sum of the degrees of the vertices of a tree is 2(n - 1)

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.