Closing a Path to Form a Cycle
A path can be colored one vertex at a time: after choosing a color for the first vertex, each later vertex has all colors available except the color of its predecessor. A cycle has one additional constraint: the last vertex must also have a different color from the first. The chromatic polynomial of a cycle measures exactly how many path colorings survive that closing condition.
All graphs here are finite and simple. A proper \(q\)-coloring assigns one of \(q\) colors to each vertex so that adjacent vertices receive different colors. For a graph \(G\), its chromatic polynomial \(P_G(q)\) is the polynomial whose value at each positive integer \(q\) is the number of proper \(q\)-colorings of \(G\). We consider \(C_n\) for \(n\ge 3\), with vertices in cyclic order.
We will fix the color of \(v_1\) and count path colorings according to whether the other endpoint \(v_k\) matches it. This keeps the closing condition visible throughout the calculation.
Endpoint Counts for a Path
Fix a positive integer \(q\) and a particular color for the first vertex of a path on \(k\) vertices. Let \(A_k\) be the number of proper path colorings in which the last vertex has that fixed color, and let \(B_k\) be the number in which the last vertex has a different color. For a one-vertex path, \(A_1=1\) and \(B_1=0\).
Proof. To extend a coloring of a path on \(k\) vertices, add one new endpoint adjacent only to the old endpoint. For the new endpoint to have the fixed first color, the old endpoint must have a different color; there is then exactly one choice for the new color. Thus \(A_{k+1}=B_k\). If the old endpoint has the fixed color, there are \(q-1\) choices for a new color different from it. If the old endpoint has a different color, there are \(q-2\) choices that differ from both the old endpoint’s color and the fixed first color. These disjoint cases give \(B_{k+1}=(q-1)A_k+(q-2)B_k\). There are \((q-1)^{k-1}\) path colorings with the first color fixed, since each of the next \(k-1\) vertices has \(q-1\) choices; hence \(A_k+B_k=(q-1)^{k-1}\). Substituting this into the formula for \(B_{k+1}\) gives \(B_{k+1}=(q-1)(A_k+B_k)-B_k=(q-1)^k-B_k\). \(\square\)
The lemma’s last recurrence alternates between a total number of path colorings and the previous endpoint count. It can be solved directly.
Proof. First take a positive integer \(q\). We claim that for every \(k\ge 1\), \(B_k=\big((q-1)^k+(-1)^k(q-1)\big)/q\). At \(k=1\), the right-hand side is \(\big((q-1)-(q-1)\big)/q=0=B_1\). Suppose the formula holds for \(k\). The recurrence gives
Thus the claimed expression for \(B_k\) holds by induction. For \(C_n\), choose the first color in \(q\) ways and color the remaining vertices along the path \(v_1v_2\cdots v_n\). The cycle-closing edge is satisfied precisely for the \(B_n\) colorings with \(v_n\) different from \(v_1\), so \(P_{C_n}(q)=qB_n=(q-1)^n+(-1)^n(q-1)\). This equality holds for every positive integer \(q\). Both sides are polynomials in \(q\), and polynomials that agree at infinitely many values are identical, proving the formula for the chromatic polynomial. \(\square\)
The argument counts endpoint relationships rather than listing colorings. The sign of the final term depends on whether \(n\) is even or odd, because the recurrence subtracts the previous endpoint count at each step.
Worked Example: The Triangle \(C_3\)
Let \(V=\{1,2,3\}\) and \(E=\{12,23,31\}\). Count the colorings directly: vertex \(1\) has \(q\) choices, vertex \(2\) has \(q-1\) choices, and vertex \(3\) must differ from both \(1\) and \(2\), leaving \(q-2\) choices. Therefore \(P_{C_3}(q)=q(q-1)(q-2)\).
The cycle formula gives \((q-1)^3-(q-1)\). Factoring and simplifying, \((q-1)\big((q-1)^2-1\big)=(q-1)(q-2)q\), which agrees with the direct count.
Check: at \(q=3\), the direct count is \(3\cdot2\cdot1=6\), and the formula gives \(2^3-2=8-2=6\).
Worked Example: The 4-Cycle \(C_4\)
Let \(V=\{1,2,3,4\}\) and \(E=\{12,23,34,41\}\). Count by first deciding whether vertices \(1\) and \(3\), which are not adjacent, have the same color. If they have the same color, there are \(q\) choices for that color, and vertices \(2\) and \(4\) each have \(q-1\) choices. This case contributes \(q(q-1)^2\). If vertices \(1\) and \(3\) have different colors, there are \(q(q-1)\) choices for them, and each of vertices \(2\) and \(4\) has \(q-2\) choices, independently. This case contributes \(q(q-1)(q-2)^2\).
Adding the disjoint cases gives \(q(q-1)\big((q-1)+(q-2)^2\big)=q(q-1)(q^2-3q+3)=q^4-4q^3+6q^2-3q\). The cycle formula gives \((q-1)^4+(q-1)\). Expanding yields \(q^4-4q^3+6q^2-4q+1+q-1=q^4-4q^3+6q^2-3q\), the same polynomial.
Check: for \(q=3\), the two cases contribute \(3\cdot2^2=12\) and \(3\cdot2\cdot1^2=6\), for a total of \(18\). The formula gives \(2^4+2=18\).
Worked Example: The 5-Cycle \(C_5\)
Let \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45,51\}\). We can verify the result using deletion and contraction. The deletion-contraction identity for an edge \(e\) states that \(P_G(q)=P_{G-e}(q)-P_{G/e}(q)\), where \(G/e\) is formed by identifying the endpoints of \(e\); here \(e=51\) is not a loop. Deleting \(51\) leaves a path on five vertices, with \(q(q-1)^4\) colorings. Contracting \(51\) leaves a 4-cycle, so the count is \(P_{C_4}(q)=q(q-1)(q^2-3q+3)\). Therefore
The final equality follows by expanding \((q-1)^5-(q-1)=(q-1)\big((q-1)^4-1\big)=q(q-1)(q-2)(q^2-2q+2)\), whose last two factors multiply to \(q^3-4q^2+6q-4\). This is the cycle formula for odd \(n=5\).
Check: at \(q=3\), the deletion term is \(3\cdot2^4=48\), while the contraction term is \(3\cdot2\cdot(9-9+3)=18\). Their difference is \(48-18=30\). The cycle formula gives \(2^5-2=32-2=30\).
Why the Closing Condition Matters
Counting colorings of the path obtained by deleting one cycle edge does not by itself count colorings of the cycle. It counts every path coloring, including those in which the two endpoints have the same color. The endpoint count \(B_n\) isolates exactly the path colorings that satisfy the missing edge. In the recurrence, this restriction is incorporated at every step rather than added as an afterthought.
The formula also gives a quick consistency check: even cycles use \((q-1)^n+(q-1)\), while odd cycles use \((q-1)^n-(q-1)\). These signs result from the parity of the number of recurrence steps; they do not mean that the two cases use different coloring rules.
Common Pitfall
Counting the path and forgetting to close it. For \(C_4\), deleting the edge \(41\) leaves a path on four vertices. With \(q=3\), that path has \(3\cdot2^3=24\) proper colorings, but this is not the cycle count: some have vertices \(1\) and \(4\) equal. The direct case count for the cycle gives \(3\cdot2^2+3\cdot2\cdot1^2=12+6=18\). The formula confirms this: \((3-1)^4+(3-1)=16+2=18\). The correction is to enforce the closing edge, not to use the path count alone.
Check Your Understanding
Use endpoint counts or a direct case split, and check each result against the cycle formula where appropriate.
- For a fixed first color, explain why \(A_{k+1}=B_k\).
- Apply the formula to \(C_6\), leaving the answer in powers of \(q-1\).
- For \(C_4\), explain why the choices for vertices \(2\) and \(4\) are independent once the colors of vertices \(1\) and \(3\) are fixed.
- Why does agreement with the formula for every positive integer \(q\) establish equality of the chromatic polynomials?
- For a cycle, which endpoint colorings of the corresponding path must be excluded, and how does \(B_n\) account for this?