GATE CSE 2017 Set 1 | Question: 20

Question

Let $T$ be a tree with $10$ vertices. The sum of the degrees of all the vertices in $T$ is ________

Comments

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.

 

---

@Nitesh Singh 2

How the above theory is applicable to this question?

---

those who are wondering why at some places…

First of all I want to clear whenever not specified in question by default binary tree is directed.

sum of degree of all nodes = 2 * number of edges

OR

 

sum of degree of all nodes = number of edges

Let’s see where to use which formula ..

Firstly , 

sum of degree of all nodes = 2 * number of edges

As you know this formula comes from graph theory and this is used whenever the neighbour of nodes is given. Like for example total no. of nodes of neighbour 2 is 10 and neighbour 1 is 11. and this formula you can apply considering binary tree as undirected because whenever neighbour is given you are counting the edges twice for each node. Let a right skewed tree of 2 nodes annotations is A(root) , B.

So, applying formula,

sum of degree of all nodes =1 (considering A) + 1 (considering 2)  

that’s why 1 edge is counted twice.So, relate it with no. of edges in formula.

---

Now, second one

sum of degree of all nodes = number of edges

whenever the degree of nodes is given. Like for example total no. of nodes of degree 2 is 10 and degree 1 is 11. and this formula you can apply considering binary tree as directed because whenever degree is given you are counting the edges single for each node. Let a right skewed tree of 2 nodes annotations is A(root) , B.

So, applying formula,

sum of degree of all nodes =1 (considering A)

here due to directed the edge is counted only once. So, relate it with no. of edges in formula.

 

Hope this helps!!!!

---

 

Let T be a tree with 10 vertices. The sum of the degrees of all the vertices in T is ________

 don’t go by the formula just make a tree with 10 vertices and check .

1-2-3-4-5-6-7-8-9-0

here  1 and 0 has degree 1 and rest 8 elements has degree 2 so total 2*8 +2 = 18.

Answer 1

Tree with $n$ vertices which means $n-1$ edges.

$n = 10 \therefore \ \text{edges} = n - 1 = 9$.

$\therefore$ Sum of degree of all vertices $\leq 2E \leq 2*9 \leq 18$

Answer is $18$

Comments

 

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.

---

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.

---

Why is it “<=” ? A/c to Handshaking lemma :

 

i.e, sum degree of all vertices is equal to twice the number of edges.

Answer 2

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

Comments

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

---

Tree with n vertices always have n-1 edges let it be max or min whatever you call it.

---

In data structures ,in the trees concept ,we used to call each every and element as node.In this case  degree of the node is the number of childrens..

But ,In GRAPH THEORY,in trees concept ,we used to call each and every element as vertex.In graph theory ,degree of the vertex is the number of edges incident on vertex(IN UNDIRECTED GRAPH).

Answer 3

Let d₁, d_2, ...d_n be a degree sequence, then

$\sum_{k=1}^{n}$ d_k = 2*(n-1) , where n = number of vertices, IFF the given graph is a tree. 

So, sum of degrees = 2*(10-1)

                                   = 18

Answer 4

sum of degree=2e

e=9 so 2*9=18.

18 is the answer.