1
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ @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$$ $\endgroup$ – Adhvaitha May 5 '15 at 15:53
  • $\begingroup$ Oh sorry, that was stupid $\endgroup$ – user160738 May 5 '15 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.