Rational Solver

0 votes

Best answer

**Recall:** We know that sum of all degree of vertices in a simple graph $G$ is twice its number of edge. Let $E(G)$ be the edge set of $G$ and $V(G)$ be the vertex set of $G$. Then

$$ \sum_{v\in G} d(v) =2|E(G)|$$

Let $T$ be a tree on $n$ vertices. By the property of tree, we know that number of edge in $T$ is $n-1$. It follows that

$$n_1(T)\times 1 +n_2(T)\times 2 + n_3(T) \times 3 + n_4(T)\times 4 = 2|E(T)|=2(n-1)$$

Further note that

$$n_1(T)+n_2(T)+n_3(T)+n_4(T) =n$$

By considering $n_2(T)=n_3(T)=n_4(T)=k$ and simplifying the above two equation yields us

$$\begin{aligned} 20+2k+3k+4k=2(n-1) &\implies 20+9k =2(20+3k-1)\\ & \implies k = 6 \end{aligned}$$

Therefore, total number of vertices in the tree is

$$n_1(T)+n_2(T)+n_3(T)+n_4(T) =20+3k = 38.$$

66 questions

23 answers

2 comments

1,801 users