We are given a simple connected graph $G(V,E)$ with vertex and edge set $V$ and $E$ respectively. For any vertex $v\in V$, let $D\_T(v)$ the degree of $v$ in a uniformly generated random spanning tree $T$ of $G$.




---


**Question:** I am interested in bounding the maximum variance of the $D\_T(v)$ over all vertices $v\in V$. I tried to find results published on this topic, but unfortunately, I could not find anything. Are you aware of some known results about it?



Random spanning trees probability problem
Here is a proof that the variance of $d\_T(v)$ does not exceed $\frac14(\deg v-1)$.


For every edge $e\in E$ take a variable $x\_e$ and consider the polynomial $$P:=\sum\_T \prod\_{e\in T} x\_e,$$
where the sum is taken over all spanning trees $T$ of $G$. It is known (see Proposition 1.1 [here](https://people.math.harvard.edu/theses/senior/mckenzie/mckenzie.pdf), for example) that $P$ is stable: it does not have vanish if all variables take values in the open upper half-plane. Real stable (that means, stable and with real coefficients) polynomials enjoy some nice properties, including the following: if you replace some variables to the real constants, you get a real stable polynomial again (or identical zero), see Theorem 2.4, p. b) [here](https://arxiv.org/pdf/2006.16847.pdf). If you assign the value 1 for each $x\_e$ where $e$ is not incident to $v$ and the value $t$ (new variable) for each $x\_e$ where $e$ is incident to $v$, you, so, get a univariate real stable polynomial $h(t)=\sum\_{T} t^{d\_T(v)}$. We have $h(0)=0$, and, since $h$ is real stable, all other roots of $h$ are non-positive real numbers: $h(t)=t(t+\alpha\_1)\ldots(t+\alpha\_k)$, where $k\leqslant \deg v-1$ (well, if the graph $G$ does not have multiple edges incident to $v$, than $k=\deg v-1$). On probabilistic language, it means that the distribution of $d\_T(v)-1$ is a convolution of $k$ Bernoulli distributions with parameters $1/(\alpha\_i+1)$. Thus the variance of $d\_T(v)-1$ equals $$\sum\_{i=1}^k\frac{\alpha\_i}{(1+\alpha\_i)^2}\leqslant \frac14 k\leqslant \frac14(\deg v-1).$$
I have seen somewhere the fact that distribution of (degree minus 1) in a random spanning tree is a convolution of Bernoullis (with above proof), but it is more difficult to remember where, than to reproduce the proof.


Note also that for fixed $n=\deg v$ the bound $(n-1)/4$ for the variance is tight, and is attained, for example (or only?) at $K\_{2,n}$.


