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 \).

Difficulty level: Easy task (using definitions and simple reasoning)
Routine calculation training
Cs translation
Send comment on task by email