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

Identify the graph

The figure is the friendship graph $F_3$ (a windmill of triangles): one central hub vertex shared by 3 triangles. It has $1 + 2\cdot 3 = 7$ vertices and $3\cdot 3 = 9$ edges. Each triangle contains the hub plus two outer vertices, and within each triangle all three vertices are mutually adjacent.

Count proper colorings with $k = 4$ colors

We count proper colorings directly (this is the chromatic polynomial $P(F_3, k)$ evaluated at $k = 4$).

Step 1 — color the hub. The central vertex can take any of the $k$ colors: $k = 4 \text{ choices.}$

Step 2 — color each triangle. Fix the hub's color. In each triangle the two outer vertices $a, b$ form an edge, and both are adjacent to the hub. So:

• $a \ne \text{hub color}$ and $b \ne \text{hub color}$,
• $a \ne b$.

Pick $a$: it must avoid the hub color, giving $k-1$ options. Then pick $b$: it must avoid both the hub color and $a$, giving $k-2$ options. So each triangle contributes $(k-1)(k-2) = 3\cdot 2 = 6 \text{ ways.}$

Step 3 — combine. The three triangles only interact through the (already fixed) hub, so their colorings are independent: $P(F_3, k) = k\,\big[(k-1)(k-2)\big]^{3}.$

With $k = 4$: $P(F_3, 4) = 4 \cdot 6^{3} = 4 \cdot 216 = 864.$

The answer is 864, option (4).

Exam trick: For any graph built by gluing blocks at a single shared (cut) vertex, color that vertex first, then multiply the independent per-block colorings. For a triangle each remaining vertex must differ from the fixed hub and from each other, giving the $(k-1)(k-2)$ factor — not $(k-1)^2$.