Tutte polynomial of a cycle
Task number: 4067
Determine the Tutte polynomial for the cycle of length \(k\).
Hint
Use the recurrence for the Tutte polynomial \( T_G (x, y) \).
\[T_G = \begin{cases} x\cdot T_{G-e} & \text{when $e$ is a bridge,} \\ y\cdot T_{G-e} & \text{when $e$ is a loop, } \\ T_{G-e} + T_{G/e} &\text{when $e$ is not a bridge nor a loop.} \end{cases} \]Furthermore, an edgeless graph has \( T_G = 1 \).
Solution
In the first step, the last option is used. So \(T_{C_k} = T_{P_{k-1}} + T_{C_{k-1}}\).
By removing leaves, we find that \(T_{P_{k-1}} = x^{k-1}\), which leads to the recurrence \(T_{C_k} = x^{k-1} + T_{C_{k-1}}\)
Lastly, we apply recurrence to the bigon, i.e. to two vertices connected by two edges. Then one vertex is left with a loop \( C_1 \), where \( T_ {C_1} = y \).
Answer
The Tutte polynomial of a cycle is: \( T_{C_k} (x, y) = x^{k-1} + x^{k-2} + \cdots + x^2 + x + y \).