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

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.

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?

• Thanks for the comment but I am still a bit lost. I know that Σdegree(V) = 2(n-1) but from here I am a lost. I feel like I am missing something very obvious here though and I am just looking past it. – MathsRookie Nov 21 '16 at 23:57
• Added some more. – Nick Peterson Nov 22 '16 at 0:12

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.