GO Classes DPP | GATE CS | Discrete Mathematics | Graph Theory

Answer 1

• We have $10$ members. The total number of possible pairs among them is $\binom{10}{2} = 45$.

• Let's create a "stranger graph" where the $10$ members are the vertices, and an edge connects two members only if they do not know each other.

• The condition "no three members are mutually strangers" means that in our stranger graph, there are no three vertices that are all connected to each other. In graph theory terms, the stranger graph must be triangle-free.

 

Now, we apply Mantel's Theorem, which states that the maximum number of edges in a triangle-free graph with $n$ vertices is $\lfloor \frac{n^2}{4} \rfloor$.

For $n = 10$, the maximum possible number of edges in the stranger graph is:

$$ \lfloor \frac{10^2}{4} \rfloor = 25 $$

This means there can be at most $\mathbf{25}$ pairs of strangers. Because there are $45$ total pairs, the remaining pairs must be people who know each other. Therefore, there must be at least $\mathbf{20}$ pairs of people who know each other ($45 - 25 = 20$).

Let's evaluate the given options based on this mathematical reality:

• A. The number of pairs of members who do not know each other is at most $\mathbf{25}$.

  This perfectly aligns with Mantel's theorem. This statement must be true.

• B. The number of pairs of members who know each other is at least $\mathbf{20}$.

  As calculated above ($45 - 25 = 20$), this is a direct consequence of the $25$-pair limit on strangers. This statement must be true.

• C. It is possible that exactly $\mathbf{20}$ pairs of members know each other.

  For this to happen, there must be exactly $25$ pairs of strangers. Mantel's Theorem's maximum bound is strictly achievable (specifically by a complete bipartite graph, $K_{5,5}$, where the $10$ members are split into two groups of $5$). Therefore, it is a mathematical possibility. This statement is true.

• D. It is possible that exactly $\mathbf{19}$ pairs of members know each other.

  For exactly $19$ pairs to know each other, there would need to be $26$ pairs of strangers ($45 - 19 = 26$). We have already proven that the absolute maximum number of stranger pairs is $25$ without forcing a triangle. Therefore, this scenario is impossible. This statement is false.