I'm trying to prove the following problem:
$v_i$ is number of vertices of degree $i$ in tree $T$. Prove that $v_1=v_3+2v_4+...+(\Delta -2)v_\Delta +2$; $\Delta$ is the max degree.
But am I not sure how. Could you please help me? My idea is to use the consequence of Eulers formula but not sure how to begin.
You can prove it by induction on the number of vertices in the tree. Suppose that it’s true for all trees with fewer than $n$ vertices, and $T$ is a tree with $n$ vertices. Let $u$ be a vertex of $T$ of degree $\Delta$, and let $u_1,\ldots,u_\Delta$ be the vertices adjacent to $u$. For $k=1\ldots,\Delta$ let $T_k$ be the subtree of $T$ induced $u$, $u_k$, and all of the vertices $w$ of $T$ such that the path from $w$ to $u$ goes through $u_k$.
Each of these trees has fewer than $n$ vertices, so the result holds for each of them. Collectively they have the same number of vertices of degrees $2$ through $\Delta-1$ as $T$, one fewer vertex of degree $\Delta$, and $\Delta$ more vertices of degree $1$, so
$$v_1+\Delta=\sum_{k=3}^\Delta(k-2)v_k-(\Delta-2)+2\Delta\,.\tag{1}$$
The numbers $v_k$ are the vertex counts for $T$. The $\Delta$ on the left is for the new vertices of degree $1$. The $\Delta-2$ on the right accounts for the loss of a vertex of degree $\Delta$. And the $2\Delta$ is the extra $+2$ terms in the $\Delta$ equations for the trees $T_1,\ldots,T_\Delta$.
Simplifying $(1)$ yields the desired result for $T$:
$$v_1=\sum_{k=3}^\Delta(k-2)v_k+2\,.$$
Hint: $v_3+2v_4+3v_5+\dots+(\Delta-2)v_\Delta+2\\=v_3+2v_4+3v_5+\dots+(\Delta-2)v_\Delta+\color{red}{2(v_1+v_2+\dots+v_\Delta)}-\color{blue}{2(v_1+v_2+\dots+v_\Delta)}+2\\=(\color{red}{v_1+2v_2}+\color{red}3v_3+\color{red}4v_4+\dots+\color{red}\Delta v_\Delta)+\color{red}{v_1}-\color{blue}{2V}+2\\=2E+\color{red}{v_1}-\color{blue}{2V}+2\\=2(E-\color{blue}V+1)+\color{red}{v_1}$
where $E,V$ is the total number of edges and vertices in the tree respectively.
