GATE CSE 2010 | Question: 1

Question

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

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

Comments

@ShamikBanerjee exactly 

---

why not B & D also 

---

@js__ The first one is not even a tree, a tree should not have multiedges , self loops or cycles.

Answer 1

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$

Comments

@yashforreal  small correction : Last line should be n1-1 = n2-1.

---

Correct, thanks for correcting that mistake

---

Since everything is same can I say graph S and T are somewhere Isomorphic in nature?? Anyone

Answer 2

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.

Comments

by handshaking theorem sum of degrees would be equal  to twice of edges now no of edges in two trees would be same it would equal to n-1 therefore sum of degrees  in both trees would be same here

Answer 3

By Handshaking Theorem, The sum of degrees would be equal to twice the no. of edges |VI = 2|E|

It is given that ξ(S) = ξ(T) then, The Sum of Degrees of vertices in G is equal to the sum of degrees of vertices in S

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

Graph G
├── Vertices: V
├── Edges: E
│
├── Subset S ⊆ V
│   └── ξ(S) = sum of degrees of vertices in S
│
├── Subset T ⊆ V
│   └── ξ(T) = sum of degrees of vertices in T

So, answer is  |S|=|T|.

Answer 4

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

Comments

@keshore muralidharan both the examples which you have given are of graphs and not of trees.

Answer 5

Draw two non isomorphic graphs like this

You can clearly see that |s| = |t| and both trees are different to each other but they satisfy the property mentioned in the question

ANSWER: C