GATE CSE
First time here? Checkout the FAQ!
x
+1 vote
120 views

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

a) (n-1)(n-2)/2
b) n(n-1)/2
c) n-1
d) n

asked in Mathematical Logic by Junior (929 points)   | 120 views

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 ..

1 Answer

+2 votes
Best answer
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)
answered by Loyal (3.9k points)  
selected by
option A is correct.


Top Users Apr 2017
  1. akash.dinkar12

    3660 Points

  2. Divya Bharti

    2580 Points

  3. Deepthi_ts

    2040 Points

  4. rude

    1966 Points

  5. Tesla!

    1768 Points

  6. Debashish Deka

    1614 Points

  7. Shubham Sharma 2

    1610 Points

  8. Prashant.

    1492 Points

  9. Arunav Khare

    1464 Points

  10. Arjun

    1464 Points

Monthly Topper: Rs. 500 gift card

22,086 questions
28,062 answers
63,294 comments
24,160 users