A tree $T$ with 50 end-vertices has an equal number of vertices of degree 2, 3, 4, and 5 but contains no vertices of degree greater than 5.

Question

What should be the order of $T$? So I know a graph $G$ is a tree if every two vertices of G are connected by a unique path

Answer 1

Say, $k$ is the number of vertices of degree 2, 3, 4 and 5 in the tree. Then, $$\Sigma_{v\in V}d(v)=(2+3+4+5)k+l$$ where $v$ are the vertices of $T$ and $l$ is the number of vertices of degree 1. But the only vertices of degree 1 in a tree are the end-vertices (if I understand correct that you mean the leafs). So, $l=50$.

Also, each tree with $n$ vertices has $n-1$ edges and we also know that $$\Sigma_{v\in V}d(v)=2|E| = 2(n-1)$$ where $E$ is the set of edges of the tree.

In the end, you get $$\Sigma_{v\in V}d(v)= 2(n-1)\Rightarrow\\ (2+3+4+5)k+50=2n-2\Rightarrow\\ 14k+52=2n\Rightarrow\\ n=7k+26$$

You also know that the number of vertices is the sum of the number of vertices with degree 1 plus the number of vertices with degree 2 plus ... plus the number of vertices with degree 5. Which means that $n=4k+l=4k+50$.

So, $4k+50=7k+26\Rightarrow k=8$ and $n=4k+50=4\cdot8+50=82$.

Answer 2

Let's make it a rooted tree with the root node having degree $5$. By definition, there are $50$ distinct root-to-leaf paths.

• A non-root vertex of degree $1$ (a leaf node) terminates a root-to-leaf path.
• A non-root vertex of degree $2$ is a "pipe" along some root-to-leaf path.
• A non-root vertex of degree $d \geq 3$ splits $1$ path into $d-1$; net difference $d-2$.

Let $k$ be the number of vertices of degree $2,3,4,5$. Counting these paths, we find: \begin{align*} 50 &= \overbrace{5}^{\text{root node}}+\sum_{\substack{v \in V(G) \setminus \{\text{root node}\} \\ \mathrm{deg}(v) \geq 3}} (\mathrm{deg}(v)-2) \\ &= 5+k+2k+3(k-1) \end{align*} which implies $k=8$.

To verify this answer is correct, we'll give a construction:

• Level 0 (1 node): $1$ node of degree $5$.
• Level 1 (5 nodes): $5$ nodes of degree $5$.
• Level 2 (20 nodes): $2$ nodes of degree $5$, and $8$ vertices of degree $4$, and $8$ vertices of degree $3$, and $2$ vertices of degree $2$.
• Level 3 (50 nodes): $6$ vertices of degree $2$, and $44$ vertices of degree $1$.
• Level 4 (6 nodes): $6$ vertices of degree $1$.

This tree has $8$ vertices of degrees $5,4,3,2$ and $50$ vertices of degree $1$.