Assume that we have ten colors to choose from. Assume that the vertices are distinguishable. How many ways are there to color the following graph? (A coloring of a graph is a painting of the vertices such that neighbors receive different colors)
What is an efficient way to approach this problem? Can I separate this situation into different cases?
Case 1: using 3 colors (this is the minimum number of colors needed to color this graph)
Case 2: using 4 colors
…
Case 7: using 9 colors (this is the maximum number of colors since there are 9 vertices)
Best Answer
Start by counting the number of ways to color the triangle. If you have $n$ colors available, you have $n$ choices for the $4$-way vertex, $n-1$ for the one above it, and $n-2$ choices for the third. Think about how many choices you have for each of the others. You will get a $9^{\text{th}}$ degree polynomial in $n$.