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

Every choice of \(3\) roads among the \(4\) towns is either a triangle, a path covering all four towns, or a star of three roads meeting at one town.

1. Triangles: choose which \(3\) of the \(4\) towns form it, \(\binom{4}{3}=4\).
2. Paths through all four towns: \(\dfrac{4!}{2}=12\).
3. Stars at one town: \(4\) choices of the common town.

Total sets of \(3\) roads \(=4+12+4=20=\binom{6}{3}\), confirming the split is exhaustive. Non-triangle sets \(=12+4=16\), which is more than \(9\).