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

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.

---

Suppose there are two vertices  v1 and v2 . If I connect them by an edge , degree of v1 increases by 1 and degree of v2 also increases by 1.

So one edge  contributed  2  extra degree in our system .

Since there are 10-1 =9 edge , so total degree =9*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.

Answer 5

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 6

Tree with n nodes cintain n-1 edges

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