  The significant progress in constructing graph spanners that are sparse
(small number of edges) or light (low total weight) has skipped spanners that
are everywhere-sparse (small maximum degree). This disparity is in line with
other network design problems, where the maximum-degree objective has been a
notorious technical challenge. Our main result is for the Lowest Degree
2-Spanner (LD2S) problem, where the goal is to compute a 2-spanner of an input
graph so as to minimize the maximum degree. We design a polynomial-time
algorithm achieving approximation factor $\tilde O(\Delta^{3-2\sqrt{2}})
\approx \tilde O(\Delta^{0.172})$, where $\Delta$ is the maximum degree of the
input graph. The previous $\tilde O(\Delta^{1/4})$ -approximation was proved
nearly two decades ago by Kortsarz and Peleg [SODA 1994, SICOMP 1998].
  Our main conceptual contribution is to establish a formal connection between
LD2S and a variant of the Densest k-Subgraph (DkS) problem. Specifically, we
design for both problems strong relaxations based on the Sherali-Adams linear
programming (LP) hierarchy, and show that "faithful" randomized rounding of the
DkS-variant can be used to round LD2S solutions. Our notion of faithfulness
intuitively means that all vertices and edges are chosen with probability
proportional to their LP value, but the precise formulation is more subtle.
  Unfortunately, the best algorithms known for DkS use the Lov\'asz-Schrijver
LP hierarchy in a non-faithful way [Bhaskara, Charikar, Chlamtac, Feige, and
Vijayaraghavan, STOC 2010]. Our main technical contribution is to overcome this
shortcoming, while still matching the gap that arises in random graphs by
planting a subgraph with same log-density.
