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)$?

| cite | improve this question | | | | |
  • 2
    $\begingroup$ 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. $\endgroup$ – 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$.

| cite | improve this answer | | | | |
  • $\begingroup$ Thanks for this concise answer @florianlehner! $\endgroup$ – Dominic van der Zypen Aug 12 '19 at 8:33


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.

| cite | improve this answer | | | | |
  • 1
    $\begingroup$ Perhaps I'm missing something, but isn't the vertex set of the graph Florian constructed, and hence also the edge set, countable? $\endgroup$ – Joshua Erde Aug 10 '19 at 10:11
  • 1
    $\begingroup$ @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. $\endgroup$ – M. Winter Aug 11 '19 at 19:02
  • $\begingroup$ Thanks @M.Winter for writing up this precise answer! $\endgroup$ – Dominic van der Zypen Aug 12 '19 at 8:33

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.