Find the probability of the event that there are at least three people who are mutually friends

Question

In a group of 5 people, every pair of them could be friends or non-friends. Assume that all possible relationships are equally likely. Find the probability of the event that there are at least three people who are mutually friends. A , B , C are mutual if A is a friend of B and C , B is a friend of A and C and C is a friend of A and b

Answer 1

Here is an approach that does not rely on Graph Theory:

Suppose we have only 3 people. What is the probability that all three are friends?

That is obviously $2^{-3}$.

Now, suppose there are 4 people. What is the probability that at least three are mutual friends? Well, let's start with the first person A. They can have 0, 1, 2, or 3 friends:

Case 1: A has 0 friends. Now, we are in the same case as above (only 3 people, all must be friends)

Probability: $\dbinom{3}{0}2^{-3}\cdot 2^{-3}$

Case 2: A has 1 friend. It is impossible to set up a set of three friends including A, so again, we are in the same case as above.

Probability: $\dbinom{3}{1}2^{-3}\cdot 2^{-3}$

Case 3: A has 2 friends. In this case, the only way for three of them to be friends is for both of A's friends to be friends. If they are not friends, since they are 2 of the remaining 3 people, it is not possible to find three people that are mutual friends.

Probability: $\dbinom{3}{2}2^{-3}\cdot 2^{-1}$

Case 4: A has 3 friends. Now, the only way for there to not be three mutual friends is if every one of them are not friends.

Probability: $\dbinom{3}{3}2^{-3}\cdot (1-2^{-3})$

Total probability among four people of having at least three mutual friends:

$$\dfrac{23}{2^6}$$

Now, suppose we add another person. That person can have 0, 1, 2, 3, or 4 friends.

Case 1: A has 0 friends, and among the remaining 4, there are at least three mutual friends.

Probability: $\dbinom{4}{0}2^{-4}\cdot \dfrac{23}{2^6}$

Case 2: A has 1 friend, and among the remaining 4, there are at least there mutual friends (note: A cannot be part of any set of three mutual friends).

Probability: $\dbinom{4}{1}2^{-4}\cdot \dfrac{23}{2^6}$

Case 3: A has 2 friends. Now, we can have those friends be friends or those friends not be friends and one of them is part of a group of mutual friends that does not include the other.

Probability: $\dbinom{4}{2}2^{-4}\left( 2^{-1}+2^{-1}(2^{-3}+2^{-3}-2^{-5})\right)$

Case 4: A has 3 friends. Now, if any of those three are also friends, we have a set of three mutual friends, but if none of them are friends, we cannot have a set of three mutual friends.

Probability: $\dbinom{4}{3}2^{-4}(1-2^{-3})$

Case 5: A has 4 friends. Again, if any of these four are also friends, we have a set of three mutual friends, but if none of them are friends, we cannot have a set of three mutual friends.

Probability: $\dbinom{4}{4}2^{-4}(1-2^{-6})$

Total probability that among 5 people, at least three are mutual friends:

$$\dfrac{636}{1024}$$

drhab's answer is much cleaner, of course.

Answer 2

A graph is bipartite if and only if it contains no odd cycle and the number of bipartite graphs having $5$ nodes equals $376$ (see here).

Let $G_{5,3}$ denote the collection of graphs that have $5$ nodes and that contain a cycle of length $3$.

Let $H_{5,5}$ denote the collection of graphs that have $5$ nodes and that contain a cycle of length $5$ and do not contain a cycle of length $3$.

Then there are $|G_{5,3}|+|H_{5,5}|=|G_{5,3}|+12$ graphs that have $5$ nodes and contain an odd cycle, so that $|G_{5,3}|+12=2^{10}-376$ or equivalently: $$|G_{5,3}|=636$$

If all graphs are equiprobable then the probability that we are dealing with a graph that has $5$ nodes and has a cycle of length $3$ equals:$$\frac{636}{1024}$$