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

Probabilistic problem on random spanning trees

Let $G(V,E)$ be a connected simple graph, where $V$ and $E$ denote respectively its vertex and the edge set respectively. 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 all connected simple graphs $G(V, E)$, all vertices $v\in V$, and all functions $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$ of $G$?