+1 vote
120 views

## Let A has n vertices. If Ā is connected graph then the maximum number of edges that A can have is

### I am getting option a , but by substitution , what is the standard way to solve it. I solve it for n=3,4 ,5 and got option a

think like ...

you have a grapg A with n vertices.  excepts one vertex, all n-1 vertices are making a complete graph with total

(n-1)(n-2)/2 edges. Now if we see complement of this graph then it would be connected right ( A' ->star graph)??

And if we add any more edge in A,  then it would make its complement disconnected ...

Note-  we are not told that A is also connected.. only A' is connected.

just give it  think ..

If  $A^c$   is connected then minimum no. of  edges in $A^c$   are n-1

so  maximum no. of edges in A= Total edges - minimum edges in $A^c$

= $_{2}^{n}\textrm{c}$ - (n-1)

=n(n-1)/2 -(n-1)

=(n-1)(n-2)/2

option A)
selected by
option A is correct.

+1 vote