{"id":"arxiv/2611.21540","url":"https://arxiv.org/abs/2611.21540","tags":["cs.DM","math.CO"],"score":0,"title":"The Sum of Leaf Weights in the Minimum Spanning Tree of the Complete Graph","domain":"cs.DM","source":"arxiv","authors":["Julia Gaudio","Phawin Prongpaophan","Miklós Z. Rácz"],"reviews":0,"subject":"cs.DM","summary":"Let $G_n$ be a random weighted complete graph on $n$ vertices, where edges have i.i.d. $\\text{Unif}(0,1)$ weights. Let $T_n$ be the Minimum Spanning Tree (MST) of $G_n$. The expected weight of $T_n$ is known to converge to $ζ(3) = \\sum_{k=1}^{\\infty} \\frac{1}{k^3}$ (Frieze 1985). We investigate the sum of weights of edges incident to the leaves of $T_n$, denoting this quantity by $L_n$. We give tight upper and lower bounds on $\\mathbb{E}[L_n]$ and determine its limit as $n$ diverges, leveraging typical behavior of sparse Erdős--Rényi random graphs. We also establish concentration of $L_n$…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-11-16","reactions":{}}