The Gateway to Computer Science Excellence
+23 votes
4.6k 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 (431k points)
edited by | 4.6k views
0

Both sentences: "the degree of a leaf is 0" and "the degree of a leaf is 1" are correct. The issue here is that they are referred to as two different subjects- Data structure & graph theory. If we interpret it with data_structure(elements are called nodes) then it is somewhat a directed graph(hierarchical Tree) so the degree of a leaf is 0 but if we interpret it with graph_theory(elements are called vertex) then it is undirected graph so the degree of a leaf is 1.

In this question it is vertex so go with graph_theory definition.

 

0

@Nitesh Singh 2

How the above theory is applicable to this question?

6 Answers

+36 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
+23
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
0

@Peeyush Pandey

@Manjeet Raj

@Sambhrant Maurya

@Tejasvi96

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

0

 

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.

0
I think the confusion arose in this thread because there are 2 definitions for the term "degree". In the context of an undirected graph, we use the term "degree of a vertex", which is the number of edges associated with that particular vertex. When it comes to a tree (binary or otherwise) we use "degree of a node" or "degree of a tree", which means the number of subtrees or the number of children originating from that node (degree of a tree is the highest number among these). Here, we have to remember that every tree is a graph and use the first definition. Because if you were to use "degree of a node", i.e number of children, you will leave out many edges while counting and end up with a lesser sum than the formula.
+9 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 (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 (457 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 (993 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,737 questions
57,385 answers
198,548 comments
105,365 users