A Combinatorial Proof of a Formula of Biane and Chapuy

Abstract

Let $G$ be a simple strongly connected weighted directed graph. Let $\mathcal{G}$ denote the spanning tree graph of $G$. That is, the vertices of $\mathcal{G}$ consist of the directed rooted spanning trees on $G$, and the edges of $\mathcal{G}$ consist of pairs of trees $(t_i, t_j)$ such that $t_j$ can be obtained from $t_i$ by adding the edge from the root of $t_i$ to the root of $t_j$ and deleting the outgoing edge from $t_j$. A formula for the ratio of the sum of the weights of the directed rooted spanning trees on $\mathcal{G}$ to the sum of the weights of the directed rooted spanning trees on $G$ was recently given by Biane and Chapuy. Our main contribution is an alternative proof of this formula, which is both simple and combinatorial.