+1 vote
14.4k views
Suppose the maximum degree of a tree $T$ is $4$. Let $n_i(T)$ denote the number of vertices having degree i. If $n_1(T) = 20$ and $n_2(T) = n_3(T) = n_4(T)$, find the number of vertices of $T$.

retagged | 14.4k views

Recall: We know that sum of all degree of vertices in a simple graph $G$ is twice its number of edge. Let $E(G)$ be the edge set of $G$ and $V(G)$ be the vertex set of $G$. Then

$$\sum_{v\in G} d(v) =2|E(G)|$$

Let $T$ be a tree on $n$ vertices. By the property of tree, we know that number of edge in $T$ is $n-1$.  It follows that

$$n_1(T)\times 1 +n_2(T)\times 2 + n_3(T) \times 3 + n_4(T)\times 4 = 2|E(T)|=2(n-1)$$

Further note that

$$n_1(T)+n_2(T)+n_3(T)+n_4(T) =n$$

By considering $n_2(T)=n_3(T)=n_4(T)=k$ and simplifying  the above two equation yields us

\begin{aligned} 20+2k+3k+4k=2(n-1) &\implies 20+9k =2(20+3k-1)\\ & \implies k = 6 \end{aligned}

Therefore, total number of vertices in the tree is

$$n_1(T)+n_2(T)+n_3(T)+n_4(T) =20+3k = 38.$$

by Professor