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).

Answer 2

Instead of directly subtracting the number of triangles from the total, we can classify every possible set of \(3\) roads (edges) among the \(4\) towns by the shape they form, and check each option against the total count.

1. Option A (7): The total number of ways to pick \(3\) edges out of the \(6\) edges of the complete graph on \(4\) towns is \(\binom{6}{3}=20\), which already exceeds \(7\), so this cannot be the count of non-triangle selections.
2. Option B (8): As shown below, the actual number of non-triangle selections works out to \(16\), so \(8\) is too small.
3. Option C (9): This is also smaller than the true count of non-triangle selections, so it is incorrect.
4. Option D (more than 9): Every set of \(3\) edges among \(4\) towns falls into exactly one of three shapes: a triangle (uses only \(3\) of the \(4\) towns), a path touching all \(4\) towns, or a "star" of \(3\) edges meeting at one town. There are \(\binom{4}{3}=4\) triangles, \(\dfrac{4!}{2}=12\) paths visiting all four towns, and \(4\) stars (one for each choice of the common town). These add up to \(4+12+4=20\), matching the total \(\binom{6}{3}=20\), which confirms the classification is complete. The non-triangle selections are the paths and stars together, \(12+4=16\), which is indeed more than \(9\).

Since the actual number of ways to avoid forming a triangle is \(16\), which is greater than \(9\), only option D is consistent with this count.

Hence, the correct answer is option D: more than 9.