Notes on Growing a Tree in a Graph

Luc Devroye, Vida Dujmović, Alan Frieze +3

We study the height of a spanning tree $T$ of a graph $G$ obtained by starting with a single vertex of $G$ and repeatedly selecting, uniformly at random, an edge of $G$ with exactl…