Question

Let, G = (V, E) be a graph. Define $\xi \left(G\right)={\sum }_d{i}_d\times d,\text{where}{i}_d$ is the number of vertices of degree d in G. If S and T are two different trees with $\xi \left(S\right)=\xi \left(T\right),\text{then}$

• A. |S| = 2|T|
• B. |S| = |T| - 1
• C. |S| = |T|
• D. |S| = |T| + 1

Answer 1

The correct option is C |S| = |T|

Given, $\xi \left(G\right)={\sum }_d{i}_d\times d=$ Sum of degrees

By handshaking theorem, $\xi \left(G\right)=2|E_G|\text{where},|E_G|$ is the number of edges in G.

If Sand T are two trees with $\xi \left(S\right)=\xi \left(T\right).$

$\Rightarrow 2|E_S|=2|E_T|$

$\Rightarrow |E_S|=|E_T|$

In a tree, $|E_S|=|S|-1\text{and}|E_T|=|T|-1$

Where |S|is number of vertices of tree S and |T| is number of veritces of tree T.

$\therefore |S|-1=|T|-1$

$\Rightarrow |S|=|T|$