Skip to main content
4 of 10
deleted 4 characters in body

Probabilistic problem on random spanning trees

We are given a connected simple graph $G(V,E)$, where $V$ and $E$ denote respectively its vertex and the edge set. Let $f: V\to \{-1,1\}$ a function mapping each vertex to a value in $\{-1,1\}$.

Let $T(E_T,V)$ be a uniformly generated random spanning tree of $G$, where $E_T\subseteq E$ denotes its edge set. Given any vertex $v\in V$, we denote by $D_T(v)$ its degree in $T$ and by $S_T(v)$ the sum of $f(v')$ over all vertices $v'$ adjacent to $v$ in $T$.


Question: How can we prove (or disprove) that, for each connected simple graph $G(V, E)$, each vertex $v\in V$, and each function $f:V\to\{1,-1\}$, we have $$\mathbb{E}[S_T(v)]\cdot\mathbb{E}\left[\frac{S_T(v)}{D_T(v)}\right]\ge 0\,,$$ where the expectation is taken over the generation of the random spanning tree $T$?