The Gateway to Computer Science Excellence
First time here? Checkout the FAQ!
x
+21 votes
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 by Veteran (418k points)
edited by | 4.1k views

6 Answers

+29 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.5k points)
edited by
+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
+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.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...
+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 (327 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 (905 points)
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
50,092 questions
55,239 answers
190,757 comments
85,992 users