Let $G=(V,E)$ be a simple, undirected graph with $\bigcup = E$ (that is, there are no isolated vertices). We say that $C\subseteq E$ is an *edge cover* of $G$ if $\bigcup C = V$. For any edge cover $C$ of $G$ we define the set of multiply covered vertices by $$\text{m}(C) = \big\{v\in V: |\{e\in C: v\in e\}|>1\big\}.$$
Is there a graph $G=(V,E)$ such that for every edge cover $C$ there is another edge cover $C'$ such that $\text{m}(C')\subseteq \text{m}(C)$, and $\text{m}(C')\neq \text{m}(C)$?



Avoiding multiply covered vertices in graph edge coverings
For $n \in \mathbb N$ Let $a\_n, b\_n$ be a pair of vertices connected by an edge. For every finite subset $M \subset \mathbb N$ take an additional vertex $v\_M$ and connect it to every vertex $a\_n$ With $n \notin M$.


Any edge cover of this graph must contain all edges $a\_nb\_n$, otherwise $b\_n$ would be uncovered. Furthermore, if there are only finitely many multiply covered $a\_n$, then there would be an uncovered $v\_M$ (namely the one which is not connected to any of them). 


On the other hand, for any infinite set $U \subseteq \mathbb N$ we can find a cover where the set of multiply covered vertices is contained in $\{a\_u \mid u \in U\}$ because any $v\_M$ has infinitely many neighbours in this set. 


In particular, since $m(C)$ is infinite, we can take any infinite strict subset $U$ of $m(C)$ and find a cover in which $m(C') \subseteq U$.


