# Existence of graph spanners

An (unweighted) $$k$$-spanner of a graph $$G$$ is a subset of edges $$S$$ such that the distance between any two vertices of $$G$$ when using only edges in $$S$$ is at most $$k$$ times the distance in graph $$G$$. The goal is to find a small set $$S$$ that satisfies this constraint.

Recently, I've looked at some algorithms for this problem such as A simple and linear time randomized algorithm for computing sparse spanners in weighted graphs. Interestingly, all of them seem to compute a $$(2k-1)$$-spanner that have at most $$O(k n^{1+1/k})$$ edges, for integers $$k\ge 1$$.

Is it impossible to construct a $$k$$-spanner for even $$k$$, e.g., $$k=2,4$$, in general graphs?
Strictly speaking it is possible to construct $$2k$$ spanners but, under some assumptions (see below), their size will never be asymptotically better than the size of the best $$2k-1$$ spanner.
Indeed, assuming Erdős Girth Conjecture, there are graphs $$G=(V,E)$$ with girth (length of the shortest cycle) $$2k+2$$ and $$\Omega(n^{1+\frac{1}{k}})$$ edges.
A $$2k$$ spanner $$S$$ of $$G$$ cannot exclude any edge $$(u,v) \in E$$. Indeed, if $$(u,v) \in E \setminus S$$, either $$u$$ and $$v$$ are disconnected in $$(V, S)$$, or their distance in $$(V, S)$$ is at least $$2k+1$$. This is a contradiction.
This means that any $$2k$$ spanner of $$G$$ must have at least $$\Omega(n^{1+\frac{1}{k}})$$ edges. However, $$O(n^{1+\frac{1}{k}})$$ edges are already enough to guarantee the existence of $$2k-1$$ spanners in any graph, as you point out.