Question

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

Short answer

Therefore, the sum of the degrees of the vertices of a tree with n vertices is \({\bf{2n - 2}}\).

Step-by-step solution

General form

Definition of tree: A tree isa connected undirected graph with no simple circuits.

Definition of rooted tree: A rooted tree is a tree in which one vertex has been designated as the root and every edge is directed away from the root.

Definition: The degree of a vertex in an undirected graph is the number of edges incident with it, except that a loop at a vertex contributes twice to the degree of that vertex. The degree of the vertex v is denoted by \({\bf{deg}}\left( {\bf{v}} \right)\).

Proof of the given statement

Suppose that a tree T has n vertices of degrees \({{\bf{d}}_{\bf{1}}}{\bf{,}}{{\bf{d}}_{\bf{2}}}{\bf{,}}...{\bf{,}}{{\bf{d}}_{\bf{n}}}\), respectively.

Because \({\bf{2e = }}\sum\limits_{{\bf{i = 1}}}^{\bf{n}} {{{\bf{d}}_{\bf{i}}}} \)and\({\bf{e = n - 1}}\).

We have,

\({\bf{2}}\left( {{\bf{n - 1}}} \right){\bf{ = 2n - 2}}\).

Conclusion: Since the sum of the degrees of the vertices is double the quantity of edges, and since a tree with n vertices has \({\bf{n - 1}}\) edges, the appropriate response is \({\bf{2n - 2}}\).