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

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

Answer 2

Tree with n nodes cintain n-1 edges

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

Answer 3

If anyone forgets to recall the property mentioned in every answer. 

Imagine a tree with a central node and remaining 9 nodes connected to it forming a star-like shape.The central node will have degree 9 and remaining nodes will have degree 1.

So it will give 9 + 9.1 = 18

---

The reason I suggested this particular example is because it is very easy and quick to draw this tree and calculate the sum of degrees and the reason why it will work is because of the fact they have mentioned just “a tree”. 

The tree I have suggested is also “a tree”.