retagged by
583 views
2 votes
2 votes
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 $F_1, \dots, F_m$ such that $A$ and $F_1$ are friends, $F_1$ and $F_2$ are friends, $\dots, F_{m−1}$ and $F_m$ are friends, and finally $F_m$ 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?
retagged by

2 Answers

2 votes
2 votes

k out of n persons are no connected anyway, that is no friendship link is available between them.

So we have to find total number of friendship links between remaining (n-k) persons.

Method 1:

each friendship involves 2 persons. At maximum possibly, each person can be connected to all other remaining (n-k-1) persons.

Which generates mesh topology. So total numberof links between (n-k) persons is:

$\frac{(n-k)(n-k-1)}{2}$

Method 2:

total ways to choose 2 persons from (n-k) persons,

$\binom{n-k}{2}=\frac{(n-k)!}{(n-k-2)!*2!}=\frac{(n-k)(n-k-1)}{2}$

Related questions

4 votes
4 votes
2 answers
4