# Avoiding multiply covered vertices in graph edge coverings

Let $$G=(V,E)$$ be a simple, undirected graph with $$\bigcup = E$$ (that is, there are no isolated vertices). We say that $$C\subseteq E$$ is an edge cover of $$G$$ if $$\bigcup C = V$$. For any edge cover $$C$$ of $$G$$ we define the set of multiply covered vertices by $$\text{m}(C) = \big\{v\in V: |\{e\in C: v\in e\}|>1\big\}.$$ Is there a graph $$G=(V,E)$$ such that for every edge cover $$C$$ there is another edge cover $$C'$$ such that $$\text{m}(C')\subseteq \text{m}(C)$$, and $$\text{m}(C')\neq \text{m}(C)$$?

• The title might be slightly misleading, as graphs in which there is a covering with $\mathrm m(C)=\varnothing$ do not have the desired property. – M. Winter Aug 9 '19 at 12:21

For $$n \in \mathbb N$$ Let $$a_n, b_n$$ be a pair of vertices connected by an edge. For every finite subset $$M \subset \mathbb N$$ take an additional vertex $$v_M$$ and connect it to every vertex $$a_n$$ With $$n \notin M$$.

Any edge cover of this graph must contain all edges $$a_nb_n$$, otherwise $$b_n$$ would be uncovered. Furthermore, if there are only finitely many multiply covered $$a_n$$, then there would be an uncovered $$v_M$$ (namely the one which is not connected to any of them).

On the other hand, for any infinite set $$U \subseteq \mathbb N$$ we can find a cover where the set of multiply covered vertices is contained in $$\{a_u \mid u \in U\}$$ because any $$v_M$$ has infinitely many neighbours in this set.

In particular, since $$m(C)$$ is infinite, we can take any infinite strict subset $$U$$ of $$m(C)$$ and find a cover in which $$m(C') \subseteq U$$.

• Thanks for this concise answer @florianlehner! – Dominic van der Zypen Aug 12 '19 at 8:33

Tl;dr

A graph with this property (let's call it property P) cannot be locally finite, that is, must have vertices of infinite degree (for an example of such a graph, see the answer of Florian Lehner).

The idea is to apply Zorn's lemma, and for that, we define a partial order on the set of all coverings:

$$C\ge\bar C\quad:\Longleftrightarrow\quad \mathrm m(C)\subset\mathrm m(\bar C).$$

Property P basically states that there is no maximal element. Assuming that $$G$$ is locally finite, I will show the contrary via Zorn's lemma. Let $$\mathfrak C$$ be a chain. In order to construct an upper bound to that chain we cannot just intersect all the $$C\in\mathfrak C$$, as they might be disjoint.

Fix a vertex $$v\in V$$ and define

$$G_i:=G[w\in V\mid \mathrm{dist}(v,w)\le i\},$$

the $$i$$-th neighborhood of $$v$$ in $$G$$.

Definition. Given a chain $$\mathfrak C$$, a subset $$\mathfrak D\subseteq \mathfrak C$$ is called end-dense, if for any $$C\in \mathfrak C$$ there is a $$D\in \mathfrak D$$ with $$D \ge C$$.

Being end-dense is transitive.

We now recursively define a decreasing sequence of chains $$\mathfrak C = \mathfrak C_0\supseteq \mathfrak C_1 \supseteq\cdots$$, so that each $$\mathfrak C_j$$ is end-dense in $$\mathfrak C_{j-1}$$. If we assume that $$G$$ is locally finite, then all the $$G_i$$ are finite. Hence, there are only finitely many possible intersections $$C\cap E(G_j),C\in\mathfrak C_{j-1}$$. Consequently, we can choose an end-dense $$\mathfrak C_j\subseteq \mathfrak C_{j-1}$$ so that all $$C\in \mathfrak C_j$$ have the same intersection $$\smash{\bar C_j}:= C\cap E(G_j)$$.

This then gives an increasing sequence $$\bar C_1\subseteq \bar C_2\subseteq \bar C_3\subseteq \cdots$$ and we can define $$\bar C := \bigcup_i \bar C_i.$$

For now, let's assume that $$G$$ is connected. I then claim, that $$\bar C$$ is a covering that upper bounds $$\mathfrak C$$:

• $$\bar C$$ is a covering: note that $$\bar C_j=\bar C\cap E(G_{j})$$ covers all the vertices in $$G_{j-1}$$, as all the neighbors of vertices in $$G_{j-1}$$ are already contained in $$G_j$$. And when we assumed $$G$$ to be connected, every vertex of $$G$$ is contained in $$G_j$$ for some $$j\ge 1$$.

• $$\bar C$$ is an upper bound: if a vertex $$v$$ is multiply covered by $$\smash{\bar C}$$, then so it is by some $$\smash{\bar C_j}$$. This $$\bar C_j$$ is induced by the infinitely many converings in $$\mathfrak C_j$$, and thus, $$v\in\mathrm m(C),C\in \mathfrak C_j$$. Since $$\mathfrak C_j$$ is end-dense in $$\mathfrak C$$ (by transitivity), we obtain that $$v$$ is multiply covered by all $$C\in \mathfrak C$$.

Consequently, $$\bar C$$ is an upper bound for $$\mathfrak C$$, and Zorn's lemma establishes the existence of a maximal element in contradiction to your property P.

What if $$G$$ is not connected? Above procedure describes how to find an upper bound on a single connected component. We can apply this to each connected component, thus finding a covering that cannot reduce its multiply covered vertices on any component. This is an upper bound for the whole graph.

• Perhaps I'm missing something, but isn't the vertex set of the graph Florian constructed, and hence also the edge set, countable? – Joshua Erde Aug 10 '19 at 10:11
• @JoshuaErde I modified my answer to now explain why the graph must have vertices of infinite degree instead of uncountably many edges. Thank you for your comment in any case. – M. Winter Aug 11 '19 at 19:02
• Thanks @M.Winter for writing up this precise answer! – Dominic van der Zypen Aug 12 '19 at 8:33