Questions: Chromatic Polynomials and Deletion-Contraction

Question 1

You compute P(G, k) = k(k−1)(k−2) for a graph G. A classmate says: 'So G has k(k−1)(k−2) proper colorings.' What is wrong with this statement?

• A. Nothing — the statement is correct as written
• B. The number of proper colorings depends on the specific value of k chosen; k(k−1)(k−2) is a formula giving a different count for each k, not a single fixed number
• C. P(G, k) counts improper colorings, not proper ones
• D. The chromatic polynomial only applies when k equals the chromatic number

Answer: (B)

This is the central misconception the topic warns against. P(G, k) is a polynomial — a function of k, not a fixed number. For k = 3, G has 3·2·1 = 6 proper colorings; for k = 4, it has 4·3·2 = 24; for k = 2, it has 2·1·0 = 0. Saying 'G has k(k−1)(k−2) proper colorings' is like saying 'the function f(x) = x² has x² outputs' — it is not wrong exactly, but it misses that k is a variable whose value you must supply. The polynomial encodes the count for every k simultaneously.

Question 2

In the deletion-contraction formula P(G, k) = P(G−e, k) − P(G/e, k), what exactly does subtracting P(G/e, k) accomplish?

• A. It removes colorings where the two endpoints of edge e have different colors
• B. It removes colorings of G−e where the two endpoints of e happen to receive the same color — colorings that would be improper in G since e requires them to differ
• C. It accounts for the fact that G/e has one fewer vertex than G−e
• D. It eliminates disconnected components from the count

Answer: (B)

The logic: P(G−e, k) counts all proper colorings of the graph without edge e, which includes cases where the endpoints u and v get the same color. Those colorings are invalid in G (since e requires u and v to differ). Colorings of G−e where u and v are the same color are exactly the colorings of G/e — merging same-colored vertices changes nothing about validity. So P(G−e, k) − P(G/e, k) = colorings of G−e that give u and v different colors = proper colorings of G. The subtraction isolates exactly the valid colorings.

Question 3

For any graph G with n vertices, the chromatic polynomial P(G, k) has degree exactly n and leading coefficient 1.

• T. True
• F. False

Answer: True

This is a structural property of chromatic polynomials. The degree equals the number of vertices because the most 'free' a coloring can be is all n vertices choosing independently from k colors (the edgeless graph gives kⁿ). Every edge constraint reduces the polynomial by one degree of freedom, but the degree itself stays n while the lower-order coefficients change. The leading coefficient is always 1, which can be seen from the fact that every graph on n vertices reduces via deletion-contraction to base cases whose leading terms all combine to give a leading coefficient of 1.

Question 4

Two non-isomorphic graphs should have different chromatic polynomials — if P(G, k) = P(H, k) for most k, then G and H are isomorphic.

• T. True
• F. False

Answer: False

This is false: two non-isomorphic graphs can coincidentally share the same chromatic polynomial. The chromatic polynomial encodes a great deal of structural information (degree, chromatic number, number of edges, bridges), but it does not uniquely determine the graph. Pairs of non-isomorphic graphs with identical chromatic polynomials are known and serve as examples that the polynomial is powerful but not a complete graph invariant. Graphs with different chromatic polynomials are definitely not isomorphic, but the converse does not hold.

Question 5

Explain in your own words why the deletion-contraction formula P(G, k) = P(G−e, k) − P(G/e, k) correctly counts proper colorings of G. What does each term represent, and why does the subtraction give the right answer?

Model answer: P(G−e, k) counts proper colorings of the graph without edge e — these are all colorings where every other adjacency constraint is satisfied, but the two endpoints u and v of e are free to be the same color or different. P(G/e, k) counts colorings of the contracted graph where u and v have been merged into a single vertex — these are exactly the colorings of G−e in which u and v received the same color (since merging same-colored vertices is equivalent). Subtracting removes these invalid cases, leaving only colorings where u and v are different colors — which are precisely the proper colorings of G, where the edge e requires them to differ.

The deletion-contraction argument is a combinatorial partition: take all colorings satisfying all constraints except e, then subtract those that violate e (same-color endpoints). The contracted graph is the clever device for counting that subset cleanly. The recursive application to base cases (edgeless graphs and complete graphs) makes the computation tractable.