Summation of intersection of graph edges

Question

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$.

Given this, how might we compute the following two sums, $\sum_{T \in \mathcal T(K_n)} |E(X) \cap E(T)|$ and $\sum_{T \in \mathcal T(K_n)} |E(X) \cap E(T)|^2$?

Answer 1

It's useful to rephrase these in terms of expected values with respect to a uniformly random tree $T \in \mathcal T(K_n)$; up to a factor of $n^{n-2} = |\mathcal T(K_n)|$, we are then looking for $\mathbb E\big[|E(X) \cap E(T)|\big]$ and $\mathbb E\big[|E(X) \cap E(T)|^2\big]$.

For every edge $e \in E(X)$, we can define a random variable $$I_e = \begin{cases}1 & e \in E(T) \\ 0 & e \notin E(T)\end{cases}$$ so that $|E(X) \cap E(T)| = \sum_{e \in E(X)} I_e$. Then $\mathbb E[I_e] = \frac{n-1}{\binom n2} = \frac 2n$ by symmetry: every edge is equally likely to be in a spanning tree, and a spanning tree contains $n-1$ out of $\binom n2$ edges. By linearity of expectation, $\mathbb E\big[|E(X) \cap E(T)|\big] = \frac{2m}{n}$.

To compute $\mathbb E\big[|E(X) \cap E(T)|^2\big]$, we need the expected value of $$\left(\sum_{e \in E(X)} I_e\right)^2$$ and this is not something we can determine from $m$ and $n$ alone. In expanding this out and applying linearity of expectation, we get

1. $m$ diagonal terms equal to $I_e^2$, whose expected value is $\mathbb E[I_e^2] = \mathbb E[I_e] = \frac 2n$;
2. some terms equal to $I_e I_{e'}$ where $e,e' \in E(X)$ are distinct edges that share one endpoint;
3. some more terms equal to $I_e I_{e'}$ where $e, e' \in E(X)$ are distinct edges that share no endpoints.

To find $\mathbb E[I_e I_{e'}]$ in the last two cases, we must find the number of spanning trees of $K_n$ that contain both $e$ and $e'$; this depends entirely on whether $e$ and $e'$ share an edge or not. Then, we must take each term as many times as there are pairs of edges of that type in $X$.