Sum of the vertex degrees for vertices of degree greater than $1$ in a tree

Question

Let $T$ be a tree with $n_1$ vertices of degree 1 and $n_2$ other vertices. Prove that the sum of the vertex degrees for the vertices of degree greater than 1 is $$n_1+2(n_2−1).$$

I'm pretty new to graph theory and am very stuck on where to even start with this question.

Any insight and help would be greatly appreciated.

Answer 1

Hint:

The sum of the vertex degrees for ANY tree on $n$ vertices is always the same. Do you know what it is?

If so, you can write $n=n_1+n_2$, plug it into the expression for the total vertex degree, and rearrange the equation to get what you need.

If you don't know the result for vertex degrees: do you know that the number of edges in a tree on $n$ vertices is always the same? If you do, then you just need to realize that each edge contributes exactly two to the total vertex degree -- one for each vertex it connects to.

Update You know that the total degree of the graph is $2(n-1)$. Therefore, we can write $$ \begin{align*} 2(n-1)&=\sum_{v\in V}\deg(v)\\ &=\sum_{v\in V_1}\deg(v)+\sum_{v\in V_2}\deg(v), \end{align*} $$ where $V_1$ is the set of vertices of degree $1$, and $V_2$ is the set of vertices of degree $2$ or more.

Now, we know that $$ \sum_{v\in V_1}\deg(v)=n_1, $$ since there are $n_1$ such vertices and each has degree $1$. So, this tells us that $$ \sum_{v\in V_2}\deg(v)=2(n-1)-n_1. $$ But, we also know that $n_1+n_2=n$. Can you see how to use this to finish up?

Answer 2

The sum of the degree of the vertices on a tree with $n$ nodes is $2(n-1)$, since there are $n-1$ edges. So we have $$ \sum_{v} \deg v = 2(n-1) $$ We can split up vertices into those that have degree $1$, and those that have degree greater than $1$. (We may assume the tree has at least two vertices, so there are no vertices of degree $0$.) So we get $$ \sum_{v \;:\; \deg v = 1} \deg v + \sum_{v \;:\; \deg v > 1} \deg v = 2(n-1) $$ i.e. $$ \sum_{v \;:\; \deg v = 1} 1 + \sum_{v \;:\; \deg v > 1} \deg v = 2(n-1). $$ How many vertices are there with $\deg v = 1$? We are given that there are $n_1$ of them. Also, convince yourself that $n = n_1 + n_2$. Plug both of these things in above and we get $$ n_1 + \sum_{v \;:\; \deg v > 1} \deg v = 2(n_1 + n_2 -1), $$ and rearranging you get the result you want.