**Edit:** ***The possible "gap" of sort in Caro and Yuster's proof of their upper bound has just been fixed!*** *See Ben Barber's comment below (and his joint paper with Daniela Kühn, Allan Lo and Deryk Osthus* [*on arXiv*][1]. *This shows Gustavsson's theorem (whose proof by Gustavsson himself might have been regarded as incomplete but was used by Caro and Yuster). So this result proves the general upper bound on the smallest coverings mentioned in Thomas Kalinowski's post is indeed correct.*

The most up to date account (except the above mentioned paper) on the minimum number of subsets for a $(v,k,2)$ covering is here:

[Y. M. Chee, C. J. Colbourn, A. C. H. Ling, R. M. Wilson, Covering and packing for pairs, *J. Combin. Theory Ser. A* **120** (2013) 1440–1449.][2]

One important remark about Thomas Kalinowski's answer is that the asymptotic solution by Caro and Yuster may be incomplete, although the claimed upper bound is likely the correct one. They rely on Gustavsson's theorem on graph decomposition (Lemma 2.1 in Caro and Yuster's paper), which is claimed to be proved in the following thesis:

T. Gustavsson, ``Decompositions of Large Graphs and Digraphs with High Minimum
Degree,'' Doctoral Dissertation, Dept. of Mathematics, Univ. of Stockholm, 1991.

However, here's an excerpt from the 2013 paper by Chee, Colbourn, Ling, and Wilson:

>Their approach relies in an essential manner on a strong statement by Gustavsson:
>
>**Proposition 1.1**: . Let $H$ be a graph with $v$ vertices and $h$ edges, having degree sequence $(d_1,\dots,d_v)$. Then there exist a constant $N_H$ and a constant $\epsilon_H>0$, both depending only on $H$, such that for all $n>N_H$, if $G$ is a graph on $n$ vertices, $m$ edges, and degree sequence $(\delta_1,\dots,\delta_n)$ so that $\min(\delta_1,\dots,\delta_n) \geq n(1−\epsilon_H)$, $\gcd(d_1,\dots,d_v)\ \vert\ \gcd(\delta_1,\dots,\delta_n)$, and $h\ \vert\ m$, then $G$ has an edge partition (decomposition) into graphs isomorphic to $H$.
>
>We have not been able to verify the proof of Proposition 1.1. Indeed, while the result has been
used a number of times in the literature, no satisfactory proof of it appears there. While we expect
that the statement is true, we do not think that the proof in [12] is sufficient at this time to employ
the statement as a foundation for further results. Therefore we adopt a strategy that is completely
independent of Proposition 1.1, and independent of the results built on it.

So, one might want to be careful about Caro and Yuster's claimed solution. Chee, Colbourn, Ling, and Wilson gave a slightly weaker upper bound on the minimum size of a $(v,k,2)$ covering, which essentially states that for sufficiently large $v$, Caro and Yuster's claimed upper bound is correct within a constant that depends on $k$. (And the proof of Gustavsson's theorem by Barber, Kühn, Lo and Osthus shows it *is* correct.) 


  [1]: http://arxiv.org/pdf/1410.5750v1.pdf
  [2]: http://dx.doi.org/10.1016/j.jcta.2013.04.005