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$. 

This made me wonder about the following:


  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.