Log In
36 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
edited by

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 Answers

85 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$

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!

@Akash Kanase can you please give source/reference of information

|S| => Here this notation means no of vertices in Graph

||S|| means no of edges.

11 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 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
0 votes

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

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
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


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


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

0 votes

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




Related questions

29 votes
6 answers
The degree sequence of a simple graph is the sequence of the degrees of the nodes in the graph in decreasing order. Which of the following sequences can not be the degree sequence of any graph? $7, 6, 5, 4, 4, 3, 2, 1$ $6, 6, 6, 6, 3, 3, 2, 2$ $7, 6, 6, 4, 4, 3, 2, 2$ $8, 7, 7, 6, 4, 2, 1, 1$ I and II III and IV IV only II and IV
asked Sep 21, 2014 in Graph Theory gatecse 8.8k views
58 votes
7 answers
A computer system has an $L1$ cache, an $L2$ cache, and a main memory unit connected as shown below. The block size in $L1$ cache is $4$ words. The block size in $L2$ cache is $16$ words. The memory access times are $2 \hspace{0.1cm} \text{nanoseconds}$ ... $888 \hspace{0.1cm} \text{nanoseconds}$ $902 \hspace{0.1cm} \text{nanoseconds}$ $968 \hspace{0.1cm} \text{nanoseconds}$
asked Apr 21, 2016 in CO and Architecture jothee 14.1k views
31 votes
5 answers
Consider a complete undirected graph with vertex set $\{0, 1, 2, 3, 4\}$. Entry $W_{ij}$ in the matrix $W$ below is the weight of the edge $\{i, j\}$ ... What is the minimum possible weight of a path $P$ from vertex $1$ to vertex $2$ in this graph such that $P$ contains at most $3$ edges? $7$ $8$ $9$ $10$
asked Apr 21, 2016 in Algorithms jothee 7.2k views
54 votes
10 answers
A hash table of length $10$ uses open addressing with hash function $h(k) = k \: mod \: 10$, and linear probing. After inserting $6$ ... insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above? $10$ $20$ $30$ $40$
asked Apr 21, 2016 in DS jothee 12.2k views