Guichard-Combinatorics-Graph-Theory · Problem 5.9.6

The chromatic polynomial counts proper colorings, and removing an edge from a complete graph $K_n$ creates a graph that's "almost complete"—two vertices can now share a color. The key insight is to use the deletion-contraction recurrence strategically: when you delete an edge from $K_n$, you get a graph where those two endpoints are independent, so you can apply the formula $P(G) = P(G - e) - P(G / e)$ to relate it back to known polynomials for $K_n$ and $K_{n-1}$.

The chromatic polynomial counts proper colorings, and removing an edge from a complete graph $K_n$ creates a graph that's "almost complete"—two vertices can now share a color. The key insight is to use the deletion-contraction recurrence strategically: when you delete an edge from $K_n$, you get a graph where those two endpoints are independent, so you can apply the formula $P(G) = P(G - e) - P(G / e)$ to relate it back to known polynomials for $K_n$ and $K_{n-1}$.