# Does every graph without isolated vertices have a minimal edge cover?

The answer is positive for finite graphs of course. In infinite graphs the matter becomes interesting. Let's revisit the definitions first.

A (simple) graph is a pair $$G=(V,E)$$, with $$V$$ being the set of vertices and $$E\subseteq\binom{V}{2}$$ being a subset of the set of unordered pairs of $$V$$. For vertices $$v,w\in V$$ we write $$vw:=\{v,w\}\in E$$ and say $$v$$ and $$w$$ are adjacent.

A subset $$S$$ of $$E$$ is called an edge cover of $$G$$ iff for any $$v\in V$$ there is a $$w\in V$$ such that $$vw\in S$$, i.e. each vertex is incident to an edge of $$S$$. Note that in a graph without isolated vertices the set of all edges is always an edge cover.

An edge cover $$S$$ of $$G$$ is called minimal iff for any subset $$T$$ of $$E$$ we have that $$T\subsetneq S$$ implies that $$T$$ is not an edge cover, i.e. no edge can be removed from $$S$$ while retaining the edge cover property.

In the finite case every graph has a minimal edge cover because the set of all edge covers is finite, there can be no infinitely descending chain of edge covers, hence there is a minimal one.

I thought I could apply Zorn's lemma for the infinite case but I'm not so sure anymore.

Let $$M$$ be the set of all edge covers of $$G$$. $$M$$ is ordered by the inclusion relation. Now if every chain $$C\subset M$$ would have a lower bound, Zorn's lemma implies that there is a minimal edge cover in $$M$$.

But given a chain $$C$$, how can I be sure about the lower bound? My original idea was to use $$T:=\bigcap_{S\in C} S$$, but since $$C$$ can have infinite cardinality, I don't even know if $$T$$ is non empty anymore. For example, take the edgeless graph $$\overline K_\omega$$ (identifying the vertices with $$\mathbb N$$) and add two vertices $$a,b\notin\mathbb N$$ connected to all vertices of $$\overline K_\omega$$ but not each other. Call that graph $$G$$ and let $$E$$ be the set of its edges (having the form $$\{a,n\}$$ or $$\{b,n\}$$). Now define an edge cover for each $$n\in\mathbb{N}$$: $$S_n:=E\setminus \{\{a,k\}:k\leq n\}$$ Now $$\{S_n\}_{n\in\mathbb N}$$ is clearly a chain, yet its intersection $$T$$ equals $$\{\{b,k\}:k\in\mathbb N\}$$, which is not an edge cover anymore because $$a$$ is not covered.

On the other hand, $$\{\{a,n\}\}\cup\{\{b,k\}:k\in\mathbb N, k\neq n\}$$ is a minimal edge cover for any $$n\in \mathbb N$$, so I'm asking:

Does every (infinite) graph without isolated vertices have a minimal edge cover?

Btw, I had no problems proving that every graph has a minimum edge cover, i.e. an edge cover with the smallest cardinality of all possible edge covers, using the minimum property of any set of ordinals.

EDIT: While bofs answer solves the problem, I would prefer a solution that does not use forbidden subgraphs.

Proof. Let $$G=(V,E)$$ be a graph without isolated vertices. Let $$M$$ be a maximal matching
in $$G$$, and let $$W$$ be the set of vertices not covered by $$M$$. For each vertex $$w\in W$$, choose an edge $$f_w\in E$$ which is incident with $$w$$. Let $$S=\{f_w:w\in W\}$$ and let $$M'$$ be the set of all edges $$e\in M$$ such that at least one endpoint of $$e$$ is not covered by $$S$$. Then $$S\cup M'$$ is a minimal edge cover of $$G$$.