 Solution

ID: past-exam-of-the-graph-theory-and-probabilistic-combinatorics-course-of-the-university-of-oxford/2007/a/2/c/solution

p_{C_{3}} = x (x - 1) (x - 2) = (x - 1)^{3} - (x - 1)

. For

n \geq 4

, deleting an edge leaves a path with polynomial

x (x - 1)^{n - 1}

, and contracting it leaves

C_{n - 1}

. Deletion-contraction and induction give

p_{C_{n}} = x (x - 1)^{n - 1} - {(x - 1)^{n - 1} + (- 1)^{n - 1} (x - 1)} = (x - 1)^{n} + (- 1)^{n} (x - 1) .

The path formula chooses its first color freely and each succeeding color in

x - 1

ways.

 New to topics? Read the docs here!