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

1 Answer 1

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$
2
  • $\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
    Commented May 31, 2019 at 11:48
  • $\begingroup$ I worked through the proof now. Really nice! $\endgroup$
    – SK19
    Commented Jun 1, 2019 at 16:17

You must log in to answer this question.

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