4
$\begingroup$

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

$\endgroup$
0

2 Answers 2

10
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ Thanks for your argument, somehow I was convinced that the intersection argument wouldn't work - and thanks to you, I learned something today! $\endgroup$ Mar 3, 2021 at 19:25
  • 1
    $\begingroup$ 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. $\endgroup$ Mar 3, 2021 at 19:26
2
$\begingroup$

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

$\endgroup$
2
  • $\begingroup$ 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. $\endgroup$ Mar 4, 2021 at 8:33
  • 1
    $\begingroup$ 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$. $\endgroup$
    – bof
    Mar 4, 2021 at 9:04

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.