2011 AMC 10A Problem 22

Note that there are only $3$ cases: all the vertices are different, there is one pair of adjacent vertices with the same colors, or there are $2$ pairs (each pair has a different color). Case $1:$ all vertices have different colors This case just gives us $6! = 720$ different colorings. Case $2:$ one pair of adjacent vertices has the same color There are $$\dfrac{6!}{2} = 360$$ ways to choose the colors for this case. There are then $5$ options for the pair of vertices. This gives us a total of $$360 \cdot 5 = 1800$$ colorings for this case. Case $3:$ two pairs of adjacent vertices have the same color There are $5$ choices for the vertex that is not in a pair. There are then $$6 \cdot 5 \cdot 4 = 120$$ choices for the colors. There are then a total of $$120 \cdot 5 = 600$$ colorings for this case. There are a total of $$720 + 1800 + 600 = 3120$$ colorings for all the cases. Thus, C is the correct answer.