(4 intermediate revisions by the same user not shown)
Line 1: Line 1:
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
+
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|
+
(A) $|S| = 2|T|$
 
 
(B) |S| = |T| - 1
+
(B) $|S| = |T| - 1$
 
 
'''(C) |S| = |T| '''
+
'''(C)$ |S| = |T| $'''
 
 
(D) |S| = |T| + 1
+
(D) $|S| = |T| + 1$
  
 
==={{Template:Author|Happy Mittal|{{mittalweb}} }}===
 
==={{Template:Author|Happy Mittal|{{mittalweb}} }}===
Line 14: Line 14:
 
<br>
 
<br>
 
<ul>
 
<ul>
<li>'''Base case''' : When $\xi(S) = \xi(T) = 1$, then we have only single node in both trees and hence |S| = |T|.</li>
+
<li>'''Base case''' : When $\xi(S) = \xi(T) = 1$, then we have only single node in both trees and hence $|S| = |T|$.</li>
<li>'''Induction hypothesis''' : Assume, for $\xi(S) = \xi(T) = k$, we have |S| = |T|.</li>
+
<li>'''Induction hypothesis''' : Assume, for $\xi(S) = \xi(T) = k$, we have $|S| = |T|$.</li>
<li>'''Induction step''' : For $\xi(S) = \xi(T) = k+1$, we must add a leaf vertex in both trees, and hence |S| = |T|.</li>
+
<li>'''Induction step''' : For $\xi(S) = \xi(T) = k+1$, we must add a leaf vertex in both trees, and hence $|S| = |T|$.</li>
 
</ul>
 
</ul>
So |S| = |T|. So option (C) is correct.
+
So $|S| = |T|$. So option (C) is correct.
  
  
Line 24: Line 24:
  
  
[[Category: Graph Theory]]
 
 
[[Category: GATE2010]]
 
[[Category: GATE2010]]
[[Category: Graph Theory questions]]
+
[[Category: Graph Theory questions from GATE]]
[[Category:Discrete Mathematics questions]]
 

Latest revision as of 11:39, 15 July 2014

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$

Solution by Happy Mittal

$\xi(G)$ basically is the sum of degrees of all vertices in a graph. If sum of degrees of two different trees are same, then number of nodes in the trees has to be same. We prove this by induction on sum of degree of all vertices in the two trees.

  • Base case : When $\xi(S) = \xi(T) = 1$, then we have only single node in both trees and hence $|S| = |T|$.
  • Induction hypothesis : Assume, for $\xi(S) = \xi(T) = k$, we have $|S| = |T|$.
  • Induction step : For $\xi(S) = \xi(T) = k+1$, we must add a leaf vertex in both trees, and hence $|S| = |T|$.

So $|S| = |T|$. So option (C) is correct.




blog comments powered by Disqus

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

Solution by Happy Mittal[edit]

$\xi(G)$ basically is the sum of degrees of all vertices in a graph. If sum of degrees of two different trees are same, then number of nodes in the trees has to be same. We prove this by induction on sum of degree of all vertices in the two trees.

So |S| = |T|. So option (C) is correct.




blog comments powered by Disqus