Given the graph, what is number of ways to color the graph with $4$ colors such that no two adjacent vertices have same color.
According to me, the inner complete graph can be colored in $4*3*2*1$ ways =$24$ ways.
Now going to outer vertices, color for vertex $A$ can be chosen in $3$ ways, color for vertex $B$ in $2$, color for $C$ in $2$ ways and color for last vertex in $1$ way. So number of ways is $3*2*2*1 = 12$ ways.
So total number of ways is $24*12 = 288$.
But this answer is wrong. I want to know where did I make a mistake. Can someone help me ?
Best Answer
Your mistake is: When coloring $B$ you don't necessarily have $2$ ways. If you have chosen $A\mapsto f$ then you still have three ways for $B$. Similarly at later stages.
We may assume $E\mapsto e$, $F\mapsto f$, $G\mapsto g$, $H\mapsto h$. The vertices $A$ and $C$ can then be colored independently in $3$ ways each. Thereby four different types emerge, each of which leads to a characteristic number of possible continuations. The types are:
Type $1$: Both $A$ and $C$ are colored $e$ or $h$. There is $1$ coloring of this type: $A\mapsto h$, $C\mapsto e$. This enforces $B\mapsto g$, $D\mapsto f$. Makes $1$ in total.
Type $2$: One of $A$ and $C$ is colored $e$ or $h$, and the other $f$ or $g$. There are $4$ colorings of this type. Assume $A\mapsto h$, $C\mapsto f$. This allows of $B\mapsto\{e,g\}$ and enforces $D\mapsto e$. Makes $8$ in total.
Type $3$: $A$ and $C$ are differently colored $f$ or $g$. There are $2$ colorings of this type. This allows of $B\mapsto\{e,h\}$, $D\mapsto\{e,h\}$. Makes $8$ in total.
Type $4$: $A$ and $C$ are equally colored $f$ or $g$. There are $2$ colorings of this type. Assume $A\mapsto f$, $C\mapsto f$. This allows of $B\mapsto\{e,g,h\}$, $D\mapsto\{e,h\}$. Makes $12$ in total.
It follows that there are $29$ colorings of the eight vertices, up to a permutation of the colors. The grand total then is $29\cdot24=696$.