Number of ways to color this graph. 

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 ?
 A: 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$.
A: We are given four colors; call them e, f, g, h.
There are 4! = 24 ways to color the four inner vertices E, F, G, H; let's assume they are colored e, f, g, h in that order. I claim there are exactly 29 ways to extend this coloring to the whole graph. It's too late and I'm too tired to write a proof of that, so I will just show that there are at least 29 by exhibiting 29 colorings which you can check.
The outer vertices A, B, C, D (in that order) can be colored in the following ways:


*

*h, g, e, f

*h, g, f, e

*f, g, e, h

*g, h, e, f

*h, e, g, f

*h, e, f, e

*h, e, g, e

*f, g, f, e

*f, g, f, h

*f, h, e, h

*g, h, e, h

*g, e, g, f

*g, h, g, f

*f, e, f, e

*f, e, f, h

*f, e, g, e

*f, e, g, h

*f, h, f, e

*f, h, f, h

*f, h, g, e

*f, h, g, h

*g, e, f, e

*g, e, f, h

*g, e, g, e

*g, e, g, h

*g, h, f, e

*g, h, f, h

*g, h, g, e

*g, h, g, h


I hope I typed that right. It was confusing of your book's author to label the outer vertices in cyclic order but not the inner vertices.
OK, there are 29 colorings. By permuting the 4 colors you get
$24\times29=696$ different colorings.
