Set cover problem with sets of size 2
This is exactly the edge cover problem, which can be solved in polynomial time by finding a maximum matching.  Then, for each unmatched vertex, add an arbitrary edge containing that vertex.

In fact, if all you want to know is whether there's an edge cover of size at most&nbsp;$k$, you don't need to construct the cover: the size of a minimum edge cover is $M + n - 2M = n-M$, where $n$&nbsp;is the number of vertices in the graph and $M$&nbsp;is the number of edges in a maximum matching.  (The reasoning here is that the cover is the $M$&nbsp;edges of the matching plus one more edge for each unmatched vertex, and there are $n-2M$ unmatched vertices.)