Suppose the maximum degree of a tree T is 4. If n1(T) = 20, n2(T) = n3(T) = n4(T), find the number of vertices of T.

Question

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

Answer 1

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