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

Consider a social network with n persons. Two persons A and B are said to be connected if either they are friends or they are related through a sequence of friends: that is, there exists a set of persons F1, . . . , Fm such that A and F1 are friends, F1 and F2 are friends, . . . . . . . ., Fm−1 and Fm are friends, and finally Fm and B are friends. It is known that there are k persons such that no pair among them is connected. What is the maximum number of friendships possible?

asked in Graph Theory by Active (2.3k points)  
recategorized by | 42 views

1 Answer

0 votes

The key idea behind this question is to think like persons are vertices and friendships between persons as edges..

So this question reduces to :

There are n vertices ; k vertices out of which is not connected to each other by any path..So we have to determine max no of edges possible under this constraint

So the idea is to exclude this k vertices first , so we are left with (n-k) vertices..

Now max possible edges among these (n-k) vertices is possible if it is a clique ; meaning every vertex is connected to all other vertices in these (n-k) vertex set..

Hence no of edges  =   n-kC2

Now we choose 1 out of those k excluded vertices , say v1and connect them to each of (n - k) vertices..Now if we go to choose any other vertex out of remaining (k-1) vertex say v2 , then that will imply having one path at least from v1 to v2 indirectly via the clique and thus violating condition..Hence we cannot connect v2 to vertices of the clique..

Hence max no of edges(friendships) possible  =  n-kC2  + (n-k)

                                                                   =  n-kC2  + n-kC1

                                                                   =  n-k+1C2  [Using identity : nCr + nCr-1 =  n+1Cr]

Hence max no of friendships possible            =   n-k+1C2 

answered by Veteran (77.2k points)  


Top Users Sep 2017
  1. Habibkhan

    7184 Points

  2. Warrior

    2664 Points

  3. Arjun

    2582 Points

  4. rishu_darkshadow

    2520 Points

  5. A_i_$_h

    2280 Points

  6. nikunj

    1980 Points

  7. manu00x

    1856 Points

  8. makhdoom ghaya

    1770 Points

  9. Bikram

    1744 Points

  10. SiddharthMahapatra

    1718 Points


26,151 questions
33,733 answers
79,971 comments
31,120 users