Question

$A,B,C,D$ are four towns, any three of which are non-colinear. In how many ways can we construct three roads (each road joins a pair of towns) so that the roads do not form a triangle?

• A. 7
• B. 8
• C. 9
• D. More than 9

Hint:

In $K_4$, the number of triangles equals $\binom{4}{3}=4$. Subtract these from all $3$-edge selections $\binom{6}{3}$ to avoid triangles.

Answer 1

The Correct Option is D

Between 4 towns there are $\binom{6}{3}=20$ ways to choose 3 roads (edges of $K_4$). A triangle occurs only when the 3 chosen roads lie among some triple of towns; there are $4$ such triangles. Thus, non-triangle selections $=20-4=16\, (\>9)$. Hence option (d).