3 votes 3 votes In a simple connected undirected graph with n nodes(where n≧2), The maximum number of nodes with distinct degrees is n-1 n-2 n-3 2 Graph Theory graph-theory graph-connectivity + – sharma.abhilasha asked Dec 15, 2015 • recategorized Jul 7, 2022 by Lakshman Bhaiya sharma.abhilasha 3.0k views answer comment Share Follow See all 0 reply Please log in or register to add a comment.
4 votes 4 votes Answer will be (A) for 3 nodes in a simple connected undirected graph degree can be 2,1,1 for 4 nodes in a simple connected undirected graph degree can be 3,2,2,1 By these degree we can draw a simple connected undirected graph (havel hakimi theorem) srestha answered Dec 15, 2015 srestha comment Share Follow See all 2 Comments See all 2 2 Comments reply Himanshu1 commented Dec 17, 2015 reply Follow Share yes , u r right .. for 5 nodes , I m getting degree sequence as 4,3,2,2,1 & for 6 nodes , as 5,4,3,3,2,1 But , Can u prove that given n vertices , we will always be able to form a simple,undirected, connected graph with n-1 distinct degrees ? 0 votes 0 votes rahul sharma 5 commented Nov 27, 2017 reply Follow Share @ 2,1,1 : Here only 2 is distinct degree node? 1 is not distinct ,it is repeated 1 votes 1 votes Please log in or register to add a comment.
1 votes 1 votes min degree of node is 1 max degree= n-1 so we have n vertices 2 vertices will have some degree acc to pigeon hole principle so max no of nodes with distinct degree= n-1 Pooja Palod answered Dec 16, 2015 Pooja Palod comment Share Follow See all 0 reply Please log in or register to add a comment.
0 votes 0 votes In a simple graph degree of each node can not be distinct. There have to be at least 2 nodes with the same degree. for e.g if i have a simple graph of 4 nodes, and i want each node to have a distinct degree then the degree sequence has to be : 3 2 1 0 but degree sequence 3 2 1 0 is impossible because if a node is having 0 degrees then the graph is not connected . also from havel hakimi we can prove that this sequence is not possible : - 3 2 1 0 -> 0 1 0 -1 => now -1 came so as per havel hakimi this degree sequence can not be possible for a simple graph. any distinct degree sequence will result in the same.. hence for n nodes at most n-1 nodes can have distinct degrees with min 2 nodes having same degrees . debasree88 answered Oct 31, 2019 debasree88 comment Share Follow See all 0 reply Please log in or register to add a comment.