# 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$$?

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.

• Thanks for your argument, somehow I was convinced that the intersection argument wouldn't work - and thanks to you, I learned something today! Mar 3, 2021 at 19:25
• This argument is almost identical to an exercise I assigned recently in my commutative algebra class: every nonzero commutative ring has a minimal prime ideal. Mar 3, 2021 at 19:26

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].$$

• Can't the argument also been taken to hypergraphs with arbitrary non-empty edges that are not necessarily finite? I mean the argument about a maximal independent set - which, as you write, converts to an argument about a minimal covering set. Mar 4, 2021 at 8:33
• A hypergraph with infinite edges need not have a minimal vertex cover or a maximal independent set. Counterexamples abound. If $V$ is an infinite set and the edges are the infinite subsets of $V$, then the independent sets are the finite subsets of $V$.
– bof
Mar 4, 2021 at 9:04