An Alternate Proof of Near-Optimal Light Spanners

In 2016, a breakthrough result of Chechik and Wulff-Nilsen [SODA '16] established that every $n$-node graph $G$ has a $(1+\epsilon )(2k-1)$-spanner of lightness $O_{\epsilon }(n^{1\mathrm{/}k})$, and recent followup work by Le and Solomon [STOC '23] generalized the proof strategy and improved the dependence on $\epsilon$. We give a new proof of this result, with the improved $\epsilon$-dependence. Our proof is a direct analysis of the often-studied greedy spanner, and can be viewed as an extension of the folklore Moore bounds used to analyze spanner sparsity.