2
$\begingroup$

If $G=(V,E)$ is a simple, undirected graph, then $C\subseteq V$ is an edge cover if $C\cap e \neq \emptyset$ for all $e\in E$.

The "best" covers in some sense are subsets $C\subseteq V$ that meet every edge in exactly one point - but in many graphs, such a nice cover does not exist; there are often "bad" edges $e$ so that $C$ covers both points of the edge (i.e. $e\subseteq C$). We define the set of bad edges with respect to an edge cover $C$ by $$\text{Bad}(C) = \{e\in E: e\subseteq C\};$$ the other edges are good with respect to $C$, that is we set $\text{Good}(C) = E\setminus\text{Bad}(C)$.

Question. Is there a connected, infinite graph $G=(V,E)$ such that for all edge covers $C$ we have $|\text{Good}(C)| < |E|$?

$\endgroup$
4
$\begingroup$

No.

The proof requires a lemma: If $C$ is an edge cover with $|\mathrm{Good}(C)| < |E|$, then it is not minimal (I can remove a point without changing the fact that it's an edge cover).

To prove the lemma, note that every "bad" edge has both its endpoints in $C$, which means that the number of bad edges is at most $|C \times C|$. Thus $|\mathrm{Good}(C)| < |E|$ implies $|\mathrm{Good}(C)| < |\mathrm{Bad}(C)| \leq |C \times C| = |C|$. Thus $C$ is bigger than the number of good edges. Since each good edge is adjacent to exactly one member of $C$, this implies there is some $v \in C$ adjacent to only bad edges. But then $C - \{v\}$ is still an edge cover.

Now, to prove that there is an edge cover $C$ with $|\mathrm{Good}(C)| = |E|$, it suffices to notice that every graph has minimal edge covers. This follows from Zorn's Lemma (you just have to check that the intersection of a decreasing chain of edge covers is still an edge cover -- and it is).

$\endgroup$
  • $\begingroup$ Beautiful lemma & conclusion - thanks Will! $\endgroup$ – Dominic van der Zypen Nov 16 '17 at 16:09

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.