# Decomposition Theorem

**Decomposition theorem**: If G = (V, E) is a connected graph and e = {a, b} ∈ E, then P(Ge, λ) = P(G, λ) P(Ge′, λ). Where Ge denotes the subgraph of G obtained by deleting e from G without removing vertices a and b.

i.e., Ge = G – e and Ge′ is a second subgraph of G obtained from Ge′ by colouring the vertices a and b.

**Proof.** Let e = {a, b}. The number of ways to properly color the vertices in Ge = G – e with (atmost) λ colours in P(Ge, λ).

Those colourings where end points a and b of e have different colours are proper colourings of G.

The colourings of Ge that are not proper colourigns of G occur when a and b have the same color. But each of these colourings corresponds with a proper colouring for Ge′. This partition of the P(Ge, λ) proper colourings of Ge into two disjoint subsets results in the equation

**P(Ge, λ) = P(G, λ) P(Ge′, λ)**

**Problem. **Using decomposition theorem find the chromatic polynomial and hence the chromatic number for the graph given below in Figure (2.73).

Solution. Deleting the edge e from G, we get G2 as shown in Figure (b). Then the chromatic polynomial of Ge is

**P(Ge, λ) = λ(λ – 1)(λ – 2)**

By colouring the endpoints of e, i.e., a and b, we get Ge′ as shown in Figure (c). Then the chromatic polynomial of Ge is

**P(Ge′, λ) = λ(λ – 1)3.**

Hence, by decomposition theorem, the chromatic polynomial of G is

P(G, λ) = λ(λ – 1)^{3} – λ(λ – 1)(λ – 2)

= λ(λ – 1) [(λ – 1)^{2}(λ – 2)]

= λ(λ – 1) – (λ^{3} – 3λ 3) λ^{4}

= 4λ^{3} 6λ – 3λ.