Spanning trees of Kn and common edges with another graph

36 Views Asked by At

We consider $X = (V,E)$ to be a simple graph on a vertex set with $n$ vertices, and edge set with $m$ edges. We denote $\mathcal T(K_n)$ to be the set of all spanning trees of $K_n$ with with vertex set $V$, and define the polynomial $P(X;x) = \frac{1}{n^{n-2}}\sum_{T \in \mathcal T(K_n)} x^{|E(X) \cap E(T)|}$.

Given this, how might we show that $P'(X;1) = 2m/n$, and that the variance of the number of edges a (uniformly random) spanning tree of $K_n$ has in common with $X$ is $\sigma^2(X) = 2m/n - 4m^2/n^2 + \left.\frac{d^2}{dx^2}P(X;x)\right|_{x=1}$?

I can see that $P'(X;1) = 2m/n$ is equivalent to showing that $\sum_{T \in \mathcal T(K_n)}|E(X) \cap E(T)| = 2mn^{n-3}$, however I don't see how to do this