I have problem stating "Find total number of ways to color a regular pentagon with 5 colors."
If we consider(Exact 5 colors to color the graph) it unlabeled graph then it will be the same to arranging 5 persons around a circular table where chairs are not numbered that is (5-1)!. But for labeled graph i am confused for this pentagon we can color first vertex with 5 and second with 4 and third with 3 so on .. so it is 5!(Wrong!), I think it is recursive problem.
But these are number of ways with exact 5 colors and i am also not sure my approach is correct or not ? Please suggest a good source or hint to learn general solutions for such coloring problems.
My question-
"Find total number of ways to color a regular pentagon with 5 colors." It is possible with at least 3 of 5 in general so what is general solution?.
Best Answer
If you are familiar with the notion of Chromatic Polynomial, this is an easy problem. You just calculate the Chromatic Polynomial of the Cycle $C_5$ : $$C_5=P_5-C_4 \,.$$
If not, here is the standard approach.
The strategy: You color vertices in order. You have 5 choices for vertex 1, 4 for vertex 2, 4 for vertex 3 ...
The problem: How many choices do we have for vertex 5? Note that the answer depends on whether vertices 1 and 4 have the same color or different colors.
The solution: Split the problem in 2: count separately the number of ways of coloring $C_5$ such that $1$ and $4$ have the same color and the number of ways of coloring $C_5$ such that $1$ and $4$ have different colors. Note that in the second case you'll need to split again in 2 and 4 have same or different colors.