We show that the techniques Thorup and Zwick used a few years ago
to construct approximate distance oracles and spanners of *weighted*
graphs, can be used to obtain spanners with sublinear error terms,
when applied to *unweighted* graphs.

More specifically, we show, for example, that for any integer k>1,
any undirected and unweighted graph G=(V,E) on n vertices has a subgraph
G'=(V,E') with O(kn^{1+1/k}) edges such that for any two vertices
u,v in V, if d_G(u,v)=d, then d_{G'}(u,v) = d + O(d^{1-1/(k-1)}.
(Here, d_G(u,v) is the distance from u to v in G.)

Our results extend, improve and simplify results of Elkin,
Elkin and Peleg, and Bolloba's, Coppersmith and Elkin.

Joint work with Mikkel Thorup.