0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – MathsRookie Nov 21 '16 at 23:57
  • $\begingroup$ Added some more. $\endgroup$ – Nick Peterson Nov 22 '16 at 0:12
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.