  We study the diameter of the graph $G(w)$ of reduced words of an element $w$
in a Coxeter group $W$ whose edges correspond to applications of the Coxeter
relations. We resolve conjectures of Reiner--Roichman and Dahlberg--Kim by
proving a tight lower bound on this diameter when $W=S_n$ is the symmetric
group and by characterizing the equality cases. We also give partial results in
other classical types which illustrate the limits of current techniques.
