# Graph theory-tree

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?

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$.
• @user160738 No. We have $$2v-2 = 2\cdot 7 + 20\cdot 100 + \sum_{i=23}^v d_i \geq 2014 + \sum_{i=23}^v 1$$ – Adhvaitha May 5 '15 at 15:53