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.8k 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 53 votes 53 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 Show 6 previous comments 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.