Arjun Suresh (talk | contribs) |
Arjun Suresh (talk | contribs) |
||
Line 24: | Line 24: | ||
− | |||
[[Category: GATE2010]] | [[Category: GATE2010]] | ||
[[Category: Graph Theory questions]] | [[Category: Graph Theory questions]] | ||
[[Category:Discrete Mathematics questions]] | [[Category:Discrete Mathematics questions]] |
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$
$\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.
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$
$\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.