1.6k views
Let $T$ be a tree with 10 vertices. The sum of the degrees of all the vertices in $T$ is ________
asked in DS | 1.6k views

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

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