Questions: Chromatic Polynomial and Counting Proper Colorings

Question 1

What is the chromatic polynomial P(K₄, k) for the complete graph on 4 vertices?

• A. k⁴
• B. k(k−1)(k−2)(k−3)
• C. k(k−1)³
• D. 4k(k−1)

Answer: (B)

In K₄, every vertex must differ from every other vertex. The first vertex gets k choices, the second k−1, the third k−2, and the fourth k−3 — giving the falling factorial k(k−1)(k−2)(k−3). Option A (k⁴) is the count without any adjacency constraints — it ignores the edges entirely. The falling factorial formula generalizes to all complete graphs: P(Kₙ, k) = k(k−1)(k−2)···(k−n+1).

Question 2

While computing P(G, 3) via deletion-contraction on edge e, you find P(G − e, 3) = 24 and P(G/e, 3) = 9. What is P(G, 3)?

• A. 33
• B. 15
• C. 216
• D. 8

Answer: (B)

The deletion-contraction formula is P(G, k) = P(G − e, k) − P(G/e, k). So P(G, 3) = 24 − 9 = 15. The common error is to add rather than subtract. The subtraction makes sense because P(G − e, k) counts all proper colorings of the graph without the edge — including those where the two endpoints of e happen to share a color. P(G/e, k) counts exactly those colorings (after merging the endpoints). Subtracting removes them, leaving only colorings where the endpoints differ, which are precisely the proper colorings of G.

Question 3

The chromatic number χ(G) equals the smallest positive integer k for which P(G, k) > 0.

• T. True
• F. False

Answer: True

This is a key structural fact: P(G, k) = 0 for k = 0, 1, ..., χ(G) − 1, because you cannot properly color G with fewer than χ(G) colors. At k = χ(G), at least one proper coloring exists, so P(G, χ(G)) > 0. This means the chromatic number is readable from the polynomial as its smallest positive integer root — a remarkable connection between the combinatorial minimum coloring problem and an algebraic object.

Question 4

The degree of the chromatic polynomial P(G, k) equals the number of edges in graph G.

• T. True
• F. False

Answer: False

The degree of P(G, k) equals the number of *vertices*, not edges. For a graph on n vertices, P(G, k) is always a degree-n polynomial with leading coefficient 1. The number of edges affects the specific coefficients (and their signs, which alternate), but not the degree. A tree on 5 vertices and a cycle on 5 vertices have the same degree polynomial — degree 5 — despite having different edge counts.

Question 5

Explain the logic behind the deletion-contraction formula P(G, k) = P(G − e, k) − P(G/e, k). Why do we subtract rather than add?

Model answer: P(G − e, k) counts all proper k-colorings of G without the constraint imposed by edge e — including colorings where the two endpoints of e share the same color. These colorings-with-shared-color correspond exactly to proper colorings of the contracted graph G/e (where the two endpoints are merged into one vertex). Subtracting P(G/e, k) removes exactly those invalid colorings, leaving only colorings where the endpoints get different colors — the proper colorings of G.

The argument is an inclusion-exclusion over whether the two endpoints of e receive the same or different colors. If different: that's a proper coloring of G, counted by P(G, k). If the same: you can treat them as one vertex, giving a proper coloring of G/e. Together these two disjoint cases cover all proper colorings of G − e, giving P(G − e, k) = P(G, k) + P(G/e, k), which rearranges to the deletion-contraction formula.