If $G=(V,E)$ is a simple, undirected graph, then $C\subseteq V$ is said to be a *vertex cover* if $C\cap e\neq \varnothing$ for all $e\in E$.


Is there an infinite graph $G=(V,E)$ such that for any vertex cover $C$ there is a vertex cover $C'\subseteq C$ with $C'\neq C$?



Infinite graph with no minimal vertex cover
No, by Zorn's Lemma!


It suffices to check that the intersection of a chain of vertex covers is a vertex cover. If the intersection $C$ fails to be a vertex cover, then there is some edge $(v,w)$ such that neither $v$ nor $w$ is in $C$. But then both $v$ and $w$ are excluded at some point in the chain, so not every set in the chain is a vertex cover.


