Log In
2 votes

In a simple connected undirected graph with n nodes(where n≧2), The maximum number of nodes with distinct degrees is

  1.  n-1
  2. n-2
  3. n-3
  4. 2
in Algorithms 1.9k views

3 Answers

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)

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 ?
@ 2,1,1 : Here only 2 is distinct degree node? 1 is not distinct ,it is repeated
1 vote
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
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 .

Related questions

0 votes
1 answer
I have a doubt in this question : I am posting this, as there is a very low probability my comment will be replied. I wanted to progress in the solution by forming the recurrence . This was my logic : T(h) : No. of nodes at height h T(l ... (h-1) + 3 This is not correct, as T(1) should be 2. It gives 5; T(0)=1 Can anynody help me with correct recurrence?
asked Sep 2, 2016 in Algorithms prasitamukherjee 94 views
0 votes
5 answers
Level of a node is distance from root to that node. For example, level of root is 1 and levels of left and right children of root is 2. The maximum number of nodes on level i of a binary tree is In the following answers, the operator '^' indicates power a) 2^i-1 b)2^i c)2^i+1 d)2^(i+1/2)
asked Jan 16, 2016 in Algorithms Akanksha Kesarwani 29.7k views
0 votes
1 answer
The number of leaf nodes in the recurrence tree of the recurence T(n) = T(n/4) + T(n/2) + n^2
asked Aug 31, 2015 in Algorithms Saurav 262 views