Minimum possible number of vertices in a tree with restrictions on vertex degree I am confused with this question. My teacher asked us at class but I cannot solve it. Can you help me?
"Let $T$ be a tree with exactly two vertices of degree $7$ and exactly $20$ vertices of degree $100.$ What is the minimum possible number of vertices in a tree $T$ that satisfies those restrictions?"
 A: Let $v$ be the number of vertices. We have the number of edges to be $v-1$ and the number of faces to be $1$. From handshake lemma, we have that
$$\sum_{i=1}^v d_i = 2(v-1)$$
We are given that $d_1=d_2=7$, $d_3=d_4=\cdots = d_{22} = 100$. This means we have $$2\cdot 7 + 20\cdot 100 + \sum_{i=23}^v d_i = 2v-2$$
Further, $d_i \geq 1$, which gives us that
$$2014+(v-22) \leq 2v-2 \implies v \geq 1994$$
Further, $v=1994$ is attained as follows. Consider a line with $22$ vertices. The left and right corner vertices are connected to $6$ leaves. The middle $20$ vertices are each connected to $98$ leaves. The total number of vertices then is given by
$$22 + 2\cdot6 + 20\cdot98 = 1994$$
Hence, the minimum number of vertices is indeed $1994$.
A: I've broken  it down into pieces for you:


*

*Any tree has one more vertex than edges. Any subgraph of a tree has at least one more vertex than edges.

*Let $G$ be the subgraph of $T$ containing the $22$ vertices mentioned in the question. Since $G$ is a subgraph of a tree it contains at most $21$ edges.

*All of the $2\times 7+20\times 100=2014$ edges mentioned in the question must be distinct unless they lie in $G$. So  $T$ contains at least $2014-21=1993$ edges and hence at least 1994 vertices.

*There exists a tree with $1994$ vertices satisfying the requirements in the question.

