4.1k views
Let $T$ be a tree with $10$ vertices. The sum of the degrees of all the vertices in $T$ is ________
in DS
edited | 4.1k 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$

Answer is $18$
by Active (4.5k points)
edited
+20
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.
+1

@Peeyush Pandey Same doubt here!

0
Same doubt
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
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...

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

by Active (2.6k points)
sum of degree=2e

e=9 so 2*9=18.

by (51 points)
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
by (327 points)
Tree with n nodes cintain n-1 edges

Sum of degrees of all vertices = 2×no of edges =2×(10-1)=18
by Junior (905 points)