Back to: Chromatic Polynomial
##### Case 1.2: Calculation of $$P_{1.2^{\circ}}(k)$$ The vertex $$E$$ cannot have a color from $$\{1,2,3\}$$. We will consider two sub-cases. In the sub-case 1.2.1 we assume that the vertex $$E$$ has the color $$4$$. In the sub-case 1.2.2 we assume that the vertex $$E$$ has one of the $$(k-4)$$ colors outside of the set $$\{1,2,3,4\}$$. Let us denote by $$P_{1.2.1^{\circ}}$$ the number of proper colorings in which the vertices $$A$$, $$B$$, $$C$$, $$D$$, $$E$$, $$G$$, and $$H$$ have the colors $$1$$, $$2$$, $$1$$, $$1$$, $$4$$, $$4$$, and $$3$$, repsectively. Denote by $$P_{1.2.2^{\circ}}(k)$$ the number of proper colorings in which the vertices $$A$$, $$B$$, $$C$$, $$D$$, $$E$$, $$G$$, and $$H$$ have the colors $$1$$, $$2$$, $$1$$, $$2$$, $$5$$, $$4$$, and $$3$$, respectively.

The number $$P_{1.2^{\circ}}(k)$$ can be expressed in terms of these newly introduced numbers as $P_{1.2^{\circ}}(k)=P_{1.2.1^{\circ}}(k)+(k-4)P_{1.2.2^{\circ}}(k).$

## Case 1.2.1: Calculation of $$P_{1.2.1^{\circ}}(k)$$ It remains to count the number of colorings for the vertex $$F$$. The vertex $$F$$ can have any color outside of $$\{1,2,4\}$$. There are $$k-3$$ such colors, hence $P_{1.2.1^{\circ}}(k)=k-3.$

##### Case 1.2.2: Calculation of $$P_{1.2.2^{\circ}}(k)$$ The vertex $$F$$ can have any color outside of the set $$\{1,2,4,5\}$$. There are $$k-4$$ available colors for $$F$$ hence $P_{1.2.2^{\circ}}(k)=k-4.$

##### Finalizing the Calculation of $$P_{1.2^{\circ}}(k)$$

Using that $$P_{1.2^{\circ}}(k)=P_{1.2.1^{\circ}}(k)+(k-4)P_{1.2.2^{\circ}}(k)$$, $$P_{1.2.1^{\circ}}(k)=k-3$$, and $$P_{1.2.2^{\circ}}(k)=k-4$$, we obtain $P_{1.2^{\circ}}(k)=k-3+(k-4)^2.$