Infinite graph with no minimal vertex cover 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$?
 A: A set $C\subseteq V$ is a minimal vertex cover of the graph $G=(V,E)$ if and only if the complement $V\setminus C$ is a maximal independent set; the existence of a maximal independent set is a straightforward consequence of Zorn's lemma.
Here is an alternative proof of the fact that every graph $G=(V,E)$ has a minimal vertex cover, using the well-ordering theorem instead of Zorn's lemma.
Let $\lt$ be a well-ordering of $V$. Define a subset $C\subseteq V$ recursively so that
$$v\in C\iff\{u\in V:u\lt v,\ uv\in E\}\not\subseteq C.$$
Plainly $C$ is a minimal vertex cover of $G$.
If we want the minimal vertex cover $C$ to be contained in a given vertex cover $C_0$, we choose a well-ordering in which every element of $V\setminus C_0$ precedes every element of $C_0$, and apply the same construction.
A similar construction works for hypergraphs with (nonempty) finite edges; just define
$$v\in C\iff\exists e\in E\ [\max e=v,\ (e\setminus\{v\})\cap C=\emptyset].$$
A: 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.
