The Gateway to Computer Science Excellence
+30 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

  1. $| S| = 2| T |$
  2. $| S | = | T | - 1$
  3. $| S| = | T | $
  4. $| S | = | T| + 1$
in Graph Theory by Boss (17.5k points)
edited by | 3.6k views

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.

2 Answers

+74 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$
by Veteran (60.9k points)
edited by
Just extra info ->

|S| => Here this notation means no of vertices in Graph. Actually it is not standard notation (Some books do not use it at all ! or even mention it ) , when First time I saw this question, I was clueless, what || meant !

Also ||S|| means no of edges.
but it is nowhere mentioned that they are talking about subset of vertices or all the vertices
i am still clueless :-) trust me i dint find any logic behind the question , i dint find any reason of |S| and |T| of not being equal and i marked the question and surprisingly my answer is right :-P i know these things shouldnot be done but i took the chance this time and was correct :-D
I came here looking for what those symbol means!
+9 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.

  / | \
 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.

by Loyal (9.9k points)
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
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,306 answers
105,009 users