Return to Answer

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

Just for fun, 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 argument 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].$$

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

Just for fun, 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.

Just for fun, 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 argument 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].$$