سوال ۱۱۷ کنکور ارشد علوم کامپیوتر ۱۳۹۸

This is the Kneser graph $K(10,3)$: vertices are the 3-element subsets of a 10-element set, and two are adjacent exactly when they are disjoint.

Count the edges directly. An edge is an unordered pair $\{A, B\}$ of disjoint 3-subsets.

• Choose the first 3-subset $A$: there are $\binom{10}{3}$ ways.
• Choose a 3-subset $B$ disjoint from $A$, i.e. inside the remaining $10-3 = 7$ elements: $\binom{7}{3}$ ways.
• Each edge is counted twice (once as $(A,B)$, once as $(B,A)$), so divide by $2$.

Cross-check (choose the support first). A disjoint pair uses $6$ distinct elements. Pick those $6$ elements in $\binom{10}{6}=210$ ways, then split them into two unordered 3-blocks in $\tfrac{1}{2}\binom{6}{3}=\tfrac{1}{2}\cdot 20 = 10$ ways:

Both methods give $2100$, which is option 1.

Pitfall: Don't forget the $\tfrac{1}{2}$. The ordered count $\binom{10}{3}\binom{7}{3}=4200$ is the trap option (4); dividing by $2$ for the unordered edge gives the correct $2100$.