Max no of edges in disconnected graph

Question

In a simple undirected graph with n vertices what is maximum no of edges that you can have keeping the graph disconnected?

A) ⁿC₂ -1

B) ⁿC₂

C) ^n-1C₂

D ^n-1C₂ - 1

Ans is C) ....Please explain how?

Comments

maximum no. of edges with n vertices = nC2

as the question ask for the maximum no. of edges for a disconnected graph :– To get that we can divide the graph into two components with (n-1) vertices and 1 vertex

Simply the connected component with (n-1) vertices will have maximum edges

i.e. (n-1)C2

Answer 1

Maximum number of edges in a complete graph = ⁿC₂

Since we have to find a disconnected graph with maximum number of edges with n vertices. Therefore our disconnected graph will have only two partions because as number of partition increases number of edges will decrease.

Now assume that First partition has x vertices and second partition has (n-x) vertices.

total number of edges = ^xC₂ +^(n-x)C₂

                                        =1/2*(2x² -2nx + n² -n),              where , 1<= x <= n-1

It would be maximum at both extreme(at x=1 or x= n-1).

Therefore, total number of edges = ⁿC₂ - (n-1) = ^n-1C₂

Comments

Can you please explain why it would be maximum at extreme ends...

Also please explain why you have subtracted  ⁿC₂-(n-1)...?

---

you can check the value by putting the different value of x and then you will get "U" type of shape. Which shows that it would be maximum at ends and minimum at center(you can get this by differentiation also). Since we got two partitions, in which one partition is complete graph with n-1 vertices and second partition is an isolated vertex. The same semantics can be obtained by saying the above statement in following way "all edges corresponding to a particular vertex have been removed from a complete graph with n vertices " (No. of edges= nC2 - (n-1) ).

---

Thanks

---

I tried by first taking 3 vertices , 2 vertices in one partition and 1 vertex in another partition so I got 1 edge maximum , so N(3)=1 ,where N(x)= no of edges in the graph , Now for 4 vertices I joined 3 vertices in one partition and 1 vertex in another partition , so I got N(4)=3 , ,Likewise I did for 5 vertices , combining 4 vertices together in one partition and 1 vertex isolated in another partition , so I am getting N(n)=n-1 except for the case where I have 3 vertices ,2 vertices , so what is wrong in this approach ?