If $G=(V,E)$ is a simple, undirected graph, then $C\subseteq V$ is an *edge cover* if $C\cap e \neq \emptyset$ for all $e\in E$.


The "best" covers in some sense are subsets $C\subseteq V$ that meet every edge in exactly one point - but in many graphs, such a nice cover does not exist; there are often "bad" edges $e$ so that $C$ covers both points of the edge (i.e. $e\subseteq C$). We define the set of *bad* edges with respect to an edge cover $C$ by $$\text{Bad}(C) = \{e\in E: e\subseteq C\};$$ the other edges are *good* with respect to $C$, that is we set $\text{Good}(C) = E\setminus\text{Bad}(C)$.


**Question.** Is there a connected, infinite graph $G=(V,E)$ such that for all edge covers $C$ we have $|\text{Good}(C)| < |E|$?



Edge covers in infinite graphs
No.


The proof requires a lemma: *If $C$ is an edge cover with $|\mathrm{Good}(C)| < |E|$, then it is not minimal (I can remove a point without changing the fact that it's an edge cover).*


To prove the lemma, note that every "bad" edge has both its endpoints in $C$, which means that the number of bad edges is at most $|C \times C|$. Thus $|\mathrm{Good}(C)| < |E|$ implies $|\mathrm{Good}(C)| < |\mathrm{Bad}(C)| \leq |C \times C| = |C|$. Thus $C$ is bigger than the number of good edges. Since each good edge is adjacent to exactly one member of $C$, this implies there is some $v \in C$ adjacent to only bad edges. But then $C - \{v\}$ is still an edge cover.


Now, to prove that there is an edge cover $C$ with $|\mathrm{Good}(C)| = |E|$, it suffices to notice that every graph has minimal edge covers. This follows from Zorn's Lemma (you just have to check that the intersection of a decreasing chain of edge covers is still an edge cover -- and it is).


