3
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

The following is an improved version of a proof I gave in a question I asked on Math Overflow about some generalizations of the present question.

Theorem. A graph (finite or infinite) without isolated vertices has a minimal edge cover.

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

$\endgroup$
  • $\begingroup$ I know nothing at all about infinite graph theory, but somehow this problem piqued my interest. I really enjoyed this proof. +1 $\endgroup$ – saulspatz May 31 '19 at 11:48
  • $\begingroup$ I worked through the proof now. Really nice! $\endgroup$ – SK19 Jun 1 '19 at 16:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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