Virtual Test Series

Question

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₁, . . . , F_m such that A and F₁ are friends, F₁ and F₂ are friends, . . . . . . . ., 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?

	(A) n−k+1C2
	(B) n-kC2
	(C) n-k-1C2
	(D) none

Answer 1

There are $k$ isolated vertices.

Maximum friendship possible is maximum number of edges present.

Therefore   ${n-k \choose 2}$ which is B.