Return to Answer

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 not just can 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 $\bar C_j:= C\cap E(G_j)$.

We then have $\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 every connected components, thus finding a covering that cannot reduce its multiply covered vertices on any component. This is an upper bound for the whole graph.

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.

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 not just can 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 $\bar C_j:= C\cap E(G_j)$.

We then have $\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, when we restrict $\mathfrak C$ to a connected component. We can apply this to every connected components, thus finding a covering that cannot reduce its multiply covered vertices on any component. This is an upper bound for the whole graph.

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 not just can 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 $\bar C_j:= C\cap E(G_j)$.

We then have $\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 every connected components, thus finding a covering that cannot reduce its multiply covered vertices on any component. This is an upper bound for the whole graph.

Delete reason: Working on fixing the answer.

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. The tricky part is to construct an upper bound to that chain (note: we cannot just intersect all the $C\in\mathfrak C$, they might be disjoint).

If we assume that $E$ is countable, we can choose an enumeration $E=\{e_1,e_2,e_3,...\}$, and define the initial segments

$$E_i:=\{e_1,...,e_i\}.$$

I need the following term

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

Note, that 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}$. Note that every covering $C\in \mathfrak C_{j-1}$ induces a covering on $E_j$, and there can be only finitely many distinct coverings on $E_j$. Consequently, we can choose an end-dense $\mathfrak C_j\subseteq \mathfrak C_{j-1}$ so that all $C\in \mathfrak C_j$ induce the same covering $\smash{\bar C_j}$ on $E_j$.

We then have $\bar C_1\subseteq \bar C_2\subseteq \bar C_3\subseteq \cdots$ and we can define $$\bar C := \bigcup_i \bar C_i.$$

I claim, that this is an upper bound for $\mathfrak C$: if a vertex $v$ is multiply covered by $\smash{\bar C}$, then so it is in some $\smash{\bar C_j}$. This $\bar C_j$ is induced by the infinitely many converings in $\mathfrak C_j\subseteq \mathfrak C$, hence $v\in\mathrm m(C),C\in \mathfrak C_j$. Since $\mathfrak C_j$ is end-dense in $\mathfrak C$, 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.

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 not just can 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 $\bar C_j:= C\cap E(G_j)$.

We then have $\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, when we restrict $\mathfrak C$ to a connected component. We can apply this to every connected components, thus finding a covering that cannot reduce its multiply covered vertices on any component. This is an upper bound for the whole graph.