Number of nodes of distinct degree

Question

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

Answer 1

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)

Comments

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

Answer 2

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

Answer 3

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 .