University of South Carolina High School Math Contest/1993 Exam/Problem 19

Problem

In the figure below, there are 4 distinct dots $A, B, C,$ and $D$, joined by edges. Each dot is to be colored either red, blue, green, or yellow. No two dots joined by an edge are to be colored with the same color. How many completed colorings are possible?

Usc93.19.PNG
$\mathrm{(A) \ }24 \qquad \mathrm{(B) \ }72 \qquad \mathrm{(C) \ }84 \qquad \mathrm{(D) \ }96 \qquad \mathrm{(E) \ }108$

Solution

There are 4 color choices for dot $A$. After coloring dot $A$, there are 3 color choices for dot $B$. If dot $D$ is the same color as dot $B$ (1 way), there are 3 choices for dot $C$. If dot $D$ is a different color from dot $B$ (2 ways), there are only 2 choices for dot $C$. Thus we have in total $4\cdot3\cdot(1\cdot3 + 2\cdot2) = 84$ possible colorings, so choice $\mathrm{(C)}$ is the answer.