38 votes 38 votes Let $T$ be a tree with $10$ vertices. The sum of the degrees of all the vertices in $T$ is ________ DS gatecse-2017-set1 data-structures tree easy numerical-answers + – Arjun asked Feb 14, 2017 retagged Dec 17, 2023 by Hira Thakur Arjun 18.7k views answer comment Share Follow See all 4 Comments See all 4 4 Comments reply Nitesh Singh 2 commented Dec 17, 2019 reply Follow Share 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. 3 votes 3 votes ayushsomani commented Jan 23, 2020 reply Follow Share @Nitesh Singh 2 How the above theory is applicable to this question? 1 votes 1 votes Kiyoshi commented May 5, 2021 reply Follow Share 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!!!! 1 votes 1 votes Pranavpurkar commented Jul 27, 2022 reply Follow Share 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. 1 votes 1 votes Please log in or register to add a comment.
Best answer 52 votes 52 votes 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$ Kantikumar answered Feb 14, 2017 edited Jun 19, 2021 by Lakshman Bhaiya Kantikumar comment Share Follow See all 9 Comments See all 9 9 Comments reply Bikram commented Feb 28, 2017 reply Follow Share 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 29 votes 29 votes Peeyush Pandey commented Jan 10, 2019 i edited by Peeyush Pandey Jan 10, 2019 reply Follow Share @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 votes 0 votes Tejasvi96 commented Jan 27, 2019 reply Follow Share 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. 0 votes 0 votes Sambhrant Maurya commented Jul 22, 2019 reply Follow Share @Peeyush Pandey Same doubt here! 1 votes 1 votes Manjeet Raj commented Sep 10, 2019 reply Follow Share Same doubt 0 votes 0 votes techbd123 commented Oct 18, 2019 reply Follow Share @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$$ 1 votes 1 votes Akash Papnai commented Nov 8, 2019 reply Follow Share 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 votes 0 votes Chinmay Agnihotri commented Dec 15, 2019 reply Follow Share 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. 8 votes 8 votes Abhrajyoti00 commented Jul 27, 2022 reply Follow Share Why is it “<=” ? A/c to Handshaking lemma : i.e, sum degree of all vertices is equal to twice the number of edges. 1 votes 1 votes Please log in or register to add a comment.
12 votes 12 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 Arnabi answered Feb 14, 2017 Arnabi comment Share Follow See all 3 Comments See all 3 3 Comments reply CHIRAG CHAWLA commented Dec 25, 2018 reply Follow Share 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... 0 votes 0 votes VYAN_jy commented Oct 21, 2022 reply Follow Share Tree with n vertices always have n-1 edges let it be max or min whatever you call it. 0 votes 0 votes Yaswanth_1 commented Nov 18, 2023 reply Follow Share 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). 0 votes 0 votes Please log in or register to add a comment.
8 votes 8 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 Uzumaki Naruto answered Feb 13, 2017 Uzumaki Naruto comment Share Follow See all 0 reply Please log in or register to add a comment.
4 votes 4 votes sum of degree=2e e=9 so 2*9=18. 18 is the answer. raktim answered Oct 12, 2017 raktim comment Share Follow See all 0 reply Please log in or register to add a comment.