The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+20 votes
3.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 (367k points)
edited by | 3.4k views

6 Answers

+27 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.7k points)
edited by
+17
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
+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 (8.1k points)
+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 (213 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

44,076 questions
49,595 answers
162,959 comments
65,791 users