Proof for coloring combinations problem. (color vertices of pentagon)

Question

While studying, I found a problem in my book that read: "Each vertex of convex pentagon ABCDE is to be colored with one of seven colors. Each end of every diagonal must have different colors. Find the number of different colorings possible."

The answer key showed the answer as 7770. The answer key also explained that you needed to find the number of ways to color the pentagon with 3, 4, and 5 colors, then add the numbers up. But other than this, no explanation was given. Could someone please give me an explanation to reaching this answer of 7770?

Answer 1

Jack D'Aurizio's answer works very well, but I see another way to solve it using chromatic polynomials. I understand that this is not the way your book wants you to solve it, but I'm posting it here for future reference:

Draw a graph with five vertices with edges connecting the vertices that cannot receive the same color. (The edges are AC, AD, BD, BE, and CE.) This graph is isomorphic to $C_5$. Then your problem is equivalent to finding the value of the chromatic polynomial of $C_5$ at $x=7$.

We know that the chromatic polynomial of $C_n$ is $(-1)^n(x-1)+(x-1)^n$. Plug in $n=5$ and $x=7$ and you get $(-1)^5(7-1)+(7-1)^5=7770$.

Answer 2

There are $7$ ways to color vertex $A$, split in two cases:

Case $1$: $D$ and $C$ have the same color, there are $6$ ways to pick that color, after this, vertices $E$ and $B$ must be distinct and must not have the color of $D$ and $C$, there are $6\cdot 5$ ways to do this, $7\cdot6\cdot6\cdot5=1260$ total.

Case $2$: $D$ and $C$ have different colors, there are $6\cdot 5$ ways to pick these colors, if $E$ and $D$ have the same color there are $6$ options for $B$ , if $E$ and $D$ have distinct colors there $5$ options for $E$ and then $5$ options for $B$ (so $6+25=31$ total). Hence there are $7\cdot6\cdot5\cdot31=6510$

Hence there are $1260+6510=7770$ total.

Answer 3

If a single colour appears more than once, it must appear at two consecutive vertices and nowhere else, hence the possible colourings fulfilling the constraints are:

• $T_0$: $ABCDE$;
• $T_1$: $AABCD$ and cyclic shifts;
• $T_2$: $AABBC$ and cyclic shifts.

There are $7\cdot 6\cdot 5\cdot 4\cdot 3 = 2520$ colourings in $T_0$, $5\cdot(7\cdot 6\cdot 5\cdot 4)=4200$ colourings in $T_1$, $5\cdot(7\cdot 6\cdot 5)=1050$ colourings in $T_3$, hence the answer is given by: $$ 2520+4200+1050 = \color{red}{7770}.$$