Q:

Graph theory question on degrees of vertices of a tree

Let $T$ be a tree with $n$ vertices and $p_i$ denote the number of vertices of degree $i$. Show that $$p_1-p_3-2p_4-...-(n-3)p_{n-1} = 2$$
I have no clue how to begin. Total degree = $2(n-1)$. Some how this will be used. And I have my suspicions on the absence of $p_2$.

A:

Sorry, just solved it.
Let $S=p_1-p_3-2p_4-...-(n-3)p_{n-1}$.
Since total degree = $2(n-1)$,
$$\begin{align*}
&p_1+2p_2+3p_3+...+(n-1)p_{n-1}=2(n-1)\\\\
\implies&p_1+2p_2+4p_3-p_3+6p_4-2p_4+8p_5-3p_5+....+(2n-4)p_{n-1}-(n-3)p_{n-1}=2n-2\\\\
\implies&S+2(p_2+2p_3+3p_4+...+(n-2)p_{n-1}=2n-2\\\\
\implies&S+2(p_2+2p_3+3p_4+...+(n-2)p_{n-1}+2\sum_{i=1}^{n-1} p_i=2n-2+2\sum_{i=1}^{n-1} p_i\\\\
\implies&S+2\sum_{i=1}^{n-1} i.p_i=2n-2+2n\\\\
\implies&S+2(2(n-1))=4n-2\\\\
\implies&S=2\;.
\end{align*}$$

