The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
+6 votes
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 (327k points) | 1.6k views

5 Answers

+13 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
answered by Loyal (4.4k points)
selected by
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
+5 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 Boss (8.2k points)
+4 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.4k points)
+1 vote
sum of degree=2e

e=9 so 2*9=18.

18 is the answer.
answered by (27 points)
0 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 anonymous

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. 

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

29,158 questions
36,985 answers
34,824 users