EXACT EXPECTATIONS OF MINIMAL SPANNING TREES
FOR GRAPHS WITH RANDOM EDGE WEIGHTS
JAMES ALLEN FILL
AND
J. MICHAEL STEELE
Abstract. Two methods are used to compute the expected value of the length
of the minimal spanning tree (MST) of a graph whose edges are assigned
lengths which are independent and uniformly distributed. The first method
yields an exact formula in terms of the Tutte polynomial. As an illustra-
tion, the expected length of the MST of the Petersen graph is found to be
34877/12012 = 2.9035 .... A second, more elementary, method for computing
the expected length of the MST is then derived by conditioning on the length
of the shortest edge. Both methods in principle apply to any finite graph.
To illustrate the method we compute the expected lengths of the MSTs for
complete graphs.
1. Introduction to a Formula
Given a finite, connected, simple graph G, we let v(G) denote the set of vertices
and let e(G) denote the set of edges. For each edge e ∈ e(G) we introduce a non-
negative random variable ξe which we view as the length of e, and we assume that
the edge lengths {ξe : e ∈ e(G)} are independent with a common distribution F . If
S(G) denotes the set of spanning trees of G and I denotes the indicator function,
then the random variable
LMST(G) = min
T∈S(G)
∑
e∈G
ξeI( e ∈ T )
is the length of the minimal spanning tree of G. In Steele (2002) a general formula
was introduced for the expected value of LMST(G).
Theorem 1. If G is a finite connected graph and the Tutte polynomial of G is
T (G;x, y), then for independent edge lengths that are uniformly distributed on [0, 1],
one has
(1)
E[LMST(G)] =
∫ 1
0
(1 − p)
p
Tx
(
G;1/p, 1/(1 − p))
T
(
G;1/p, 1/(1 − p)) dp,
where Tx(x, y) denotes the partial derivative of T (x, y) with respect to x.
The next few sections will provide a self-contained proof of this result. The for-
mula is then applied to several concrete examples, including—for novelty’s sake—
the famous Petersen graph. We then focus on Kn, the complete graph on n vertices.
In particular, we show how a