Graph theory and degree of vertex

83 Views Asked by At

A given tree with 9 vertices has precisely five vertices of degree 1, and precisely two vertices of degree 2. The remaining two vertices have degrees $a$ and $b$. Given that $a \le b$, determine $a$ and $b$.

1

There are 1 best solutions below

4
On BEST ANSWER

For $d \ge 1$, let $n_d$ be the number of vertices of degree $d$. Then \begin{align} \sum_d n_d &= 9 \\ \sum_d d n_d &= 2(9-1) \end{align} Substituting $n_1=5$ and $n_2=2$ yields $$1\cdot 5 + 2\cdot 2 + a + b = 16,$$ so $$a + b = 7.$$ Now what does $3 \le a \le b$ imply?