The Gateway to Computer Science Excellence
+21 votes
Let $T$ be a tree with $10$ vertices. The sum of the degrees of all the vertices in $T$ is ________
in DS by Veteran (423k points)
edited by | 4.2k views

6 Answers

+30 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$
by Active (4.6k points)
edited 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

@Shaik Masthan sir, in this example 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??

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.

@Peeyush Pandey Same doubt here!

Same doubt

@Peeyush Pandey

@Manjeet Raj

@Sambhrant Maurya


Here it's a tree NOT necessarily a directed binary tree which has a node having $0$, $1$ or $2$ degrees. So using Handshake Lemma for any general tree having $n$ nodes has the total degrees $$D=2|E|=2(n-1)=2*(10-1)=18$$



Outgoing edges of 2 are 3 (arrows in dotted lines)

Similarly, outgoing edges of 3 are 3

outgoing edges of 4,5,6,7 is 1

outgoing edges of 1 are 2.

Just see number of lines connected to particular node for outgoing edges.

+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
by Loyal (7.9k points)
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

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

e=9 so 2*9=18.

18 is the answer.
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
by (377 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
by Junior (925 points)
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
50,650 questions
56,185 answers
94,693 users