Number of vertices in tree

Question

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.

Answer 1

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\,.$$

Answer 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.