Tutte polynomial of a multiedge

Task number: 4068

Determine the Tutte polynomial for two vertices connected by \( k \) edges.

  • Hint

    Use the recurrent relation to calculate the Tutte polynomial.

  • Solution

    Let us denote the two vertices connected by \( k \) edges by \( B_k \). Next, let’s denote the vertex with \( k \) loops as \( L_k \).

    In the first step, the last option is used, i.e. \( T_{B_k} = T_{B_{k-1}} + T_{L_{k-1}} \).

    By removing the loops, we find that \( T_{L_{k-1}} = y^{k-1} \).

    The recurrence stops after we apply it on the bigon (two vertices connected by two edges). Then we obtain a path \( P_1 \). We apply the first rule where \( T_{P_1} = x \).

  • Answer

    Tutte polynomial of a multi-edge is \( T_{B_k} (x, y) = x + y^{k-1} + y^{k-2} + \cdots + y^2 + y \).

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