The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+21 votes
4k views
Let $T$ be a tree with $10$ vertices. The sum of the degrees of all the vertices in $T$ is ________
asked in DS by Veteran (408k points)
edited by | 4k views

7 Answers

+28 votes
Best answer
Tree with $n$ vertices which means $n-1$ edges.

$n = 10 \therefore \ edges = n - 1 = 9$.

$\therefore$ Sum of degree of all vertices $\leq 2E \leq 2*9 \leq 18$

Answer is $18$
answered by Active (4.5k points)
edited by
+18
it is 18 for sure.

Sum of degrees of all vertices = twice the number of edges = 2e we know,

now e = n-1

here n = 10 given

hence 2e = 2(n-1) = 2*9 = 18
0

@Shaik Masthan sir, in this example https://gateoverflow.in/3548/gate2006-it-9 Arjun sir said "In tree degree is for outgoing edges only, and hence each degree corresponds to an edge" that means we have to count 0 for leaves

by this definition i am getting answer as 9 but answer given is 18.

is there any default case??

0
yeah exactly. I have the same doubt and confused regarding the degree of the tree whether it is equal to the number of edges or we should use the handshaking lemma just as in other graph.
+8 votes
A tree with n vertices can have maximum of n-1 edges.

Now by Handshaking Lemma we know sum of degrees of all vertices <= 2E<=2(n-1)<=2*(10-1)<=18

Ans: 18
answered by Loyal (7.8k points)
0
Degree of a node of a tree is the number of childrens it has.

So according to this sum of all degrees should be equal to number of edges.

Correct me if I am wrong...
+7 votes

Let d1, d2, ...dn be a degree sequence, then

$\sum_{k=1}^{n}$ dk = 2*(n-1) , where n = number of vertices, IFF the given graph is a tree. 

So, sum of degrees = 2*(10-1)

                                   = 18

answered by Active (2.6k points)
+4 votes
sum of degree=2e

e=9 so 2*9=18.

18 is the answer.
answered by (51 points)
+3 votes
Use sum of degree theorem to:- for a graph,  total sum of degree is = 2 * total edges
so here the number of nodes=10
so edge (E)=10-1=9
so the sum of degree should be like
sum of degree <=2*E => sum of degree <= 18
answered by (307 points)
0 votes
Tree with n nodes cintain n-1 edges

Sum of degrees of all vertices = 2×no of edges =2×(10-1)=18
answered by Junior (857 points)
–2 votes
I think the answer should be 9. As it is a tree, the degree of a node/vertex is the number of child nodes it has and the parent is not taken into consideration. Thus, Handshaking lemma can not be applied as it is not a graph.

Try arranging the nodes in any way possible the summation of degrees of all the node will equal to (n-1) for a tree with n nodes.
answered by
+2

When nothing is given, by default it is undirected. It can be any tree.  Just imagine a structure like spanning tree. 
That is also a tree. So here it means a undirected tree so answer is 18. 

+1

Can tree $T$ looks like this

please correct me if I'm wrong?

0
Yes it is correct, you can assume any tree.
Answer:

Related questions

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
49,587 questions
54,197 answers
187,535 comments
71,152 users