Dark Mode

8,365 views

47 votes

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

- $| S| = 2| T |$
- $| S | = | T | - 1$
- $| S| = | T | $
- $| S | = | T| + 1$

*An observation:*

*There is nothing in the Q from which we can do any comparison between |S| and |T|, I mean S is one tree and T is another, nothing is specifically given about them. Like saying no of vertices for one is half of the other or 1 less than the other.*

*So, A, B, D can be ruled out.*

*C is the **ans**.*

4

97 votes

Best answer

Sum of degrees in a graph $= 2 |E|$, as each edge contributes two to the sum of degrees. So, when sum of degrees are same, number of edges must also be same.

Trees with equal no of edges has to have equal no of vertices as No of Edges $=$ No of vertices $- 1$, in a tree.

So, should be $|S| = |T|$

Correct Answer: $C$

Trees with equal no of edges has to have equal no of vertices as No of Edges $=$ No of vertices $- 1$, in a tree.

So, should be $|S| = |T|$

Correct Answer: $C$

Here is what I found supporting @Akash Kanase Sir’s point!

see this → https://faculty.math.illinois.edu/~west/igt/notat.html

0

12 votes

The expression ξ(G) is basically sum of all degrees in a tree. For example, in the following tree, the sum is 3 + 1 + 1 + 1.

a / | \ b c d

Now the questions is, if sum of degrees in trees are same, then what is the relationship between number of vertices present in both trees? The answer is, ξ(G) and ξ(T) is same for two trees, then the trees have same number of vertices. It can be proved by induction. Let it be true for n vertices. If we add a vertex, then the new vertex (if it is not the first node) increases degree by 2, it doesn't matter where we add it. For example, try to add a new vertex say 'e' at different places in above example tee.

1 vote

id= no. of vertices of degree ‘d’ in ‘G’

Eg:

No. of vertices with degree ‘2’ = 3

ξ(G')=3×2='6' i.e., sum of degrees

By Handshaking Theorem,

The sum of degrees would be equal to twice the no. of edges

|V|=2|E|

It is given that ξ(G)=ξ(S) then

Sum of degrees of vertices in G is equal to sum of degrees of vertices in S

i.e., 2*(no. of edges in G)=2*no. of edges in S no. of edges in G=no. of edges in S

Eg:

ξ(G)=(2×2)+(2×3)=4+6=10

ξ(S)=2×5=10

You can observe that, though no. of vertices are different, but still no. of edges are same