The Gateway to Computer Science Excellence
+2 votes
1.4k views

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 by (39 points) | 1.4k 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)

by Veteran (119k points)
0
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 ?
+1
@ 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
by Boss (31.4k points)
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 .
by (287 points)
Quick search syntax
tags tag:apple
author user:martin
title title:apple
content content:apple
exclude -tag:apple
force match +apple
views views:100
score score:10
answers answers:2
is accepted isaccepted:true
is closed isclosed:true
50,737 questions
57,312 answers
198,343 comments
105,036 users