The Number of 0-1-2 Increasing Trees as Two Different Evaluations of the Tutte Polynomial of a Complete Graph

Abstract

If $T_{n}(x,y)$ is the Tutte polynomial of the complete graph $K_n$, we have the equality $T_{n+1}(1,0)=T_{n}(2,0)$. This has an almost trivial proof with the right combinatorial interpretation of $T_{n}(1,0)$ and $T_{n}(2,0)$. We present an algebraic proof of a result with the same flavour as the latter: $T_{n+2}(1,-1)=T_n(2,-1)$, where $T_{n}(1,-1)$ has the combinatorial interpretation of being the number of 0–1–2 increasing trees on $n$ vertices.