2
$\begingroup$

If $G=(V,E)$ is a simple, undirected graph, $C\subseteq V$ is said to be a vertex cover if for every $e\in E$ we have $C\cap e \neq \emptyset.$

If $G=(V,E) $ is infinite, is there necessarily a vertex cover $C_0\subseteq V$ of $G$ such that for every $v\in C_0$ we have that $C_0\setminus\{v\}$ is no longer a vertex cover of $G$?

$\endgroup$

1 Answer 1

1
$\begingroup$

Yes: take an inclusion-maximal independent set (exists by Zorn lemma) and pass to a complement.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .