Different trees of weighted graph , please check whether my explanation is correct $?$

95 Views Asked by At

Let G=(V, E) be a graph. Define $\xi(G) = \sum\limits_d i_d*d$, where $i_d$ is the number of vertices of degree $d$ in G. If S and T are two different trees with $\xi(S) = \xi(T)$, then

Options are $:$

  1. $|S| = 2|T|$
  2. $|S| = |T| - 1$
  3. $|S| = |T|$
  4. $|S| = |T| + 1$

I try to explain $:$

Given , sum of degrees of two different tree of same graph ,so number of edges will be equal , and number of vertices is equal also . Hence , option $(3)$ is true .


Please check whether my explanation is correct $?$

1

There are 1 best solutions below

1
On BEST ANSWER

Your understanding is correct, but the reasoning could be explained more clearly:

Clearly $\xi(G)$ is the sum of the degrees of the vertices of $G$, which is twice the number of edges. Thus, if $\xi(S)=\xi(T)$, then $S$ and $T$ have the same number of edges, $\frac{\xi(S)}2$. The number of vertices of a tree is one more than the number of edges, so $|S|=\frac{\xi(S)}2+1=\frac{\xi(T)}2+1=|T|$.