1
$\begingroup$

How can it be proved that any minimum edge cover is a forest? As far as I understand an edge cover could be one connected component therefore a spanning tree). If it's the case then it wouldn't be a forest.

$\endgroup$
2
$\begingroup$

A forest is a graph in which every component is a tree. If there is only one component, and that component is a tree, the graph is a forest.

So why is every minimum edge cover a forest? Suppose you have a graph $G=(V,E)$ and an edge cover $C\subseteq E$. Suppose some component of the graph $(V,C)$ contains a cycle, say $x_1x_2\dots x_kx_1$. Then $C\setminus\{x_1x_2\}$ is a smaller edge cover than $C$: $x_1$ is covered by the edge $x_kx_1$, $x_2$ is covered by $x_2x_3$ and every other vertex in $V$ is still covered by whatever covered it in $C$. Therefore, every minimum edge cover must contain no cycles, and an undirected graph that contains no cycles is a forest.

Indeed, we can go even farther. If an edge cover $C$ contains a path $x_1x_2x_3x_4$ then $C\setminus\{x_2x_3\}$ is a smaller edge cover, by essentially the same reasoning as above. Therefore any minimal edge cover is a forest that contains no path of three or more edges. So, not only is every minimum edge cover a forest, but it's a forest where every component is a star (a complete bipartite graph $K_{1,k}$ for some $k\geq 1$; note that $K_{1,1}$ is an edge and $K_{1,2}$ is a two-edge path).

$\endgroup$
  • $\begingroup$ but according to that logic a spanning tree is a also a forest. then what is the difference between spanning tree and edge cover? $\endgroup$ – Yos Jan 25 '18 at 13:41
  • 1
    $\begingroup$ A spanning tree is a tree so it is connected by definition. An edge cover doesn't have to be connected, and a non-minimal edge cover doesn't even have to be a forest. $\endgroup$ – David Richerby Jan 25 '18 at 13:54
  • $\begingroup$ it seems like the proof is almost trivial in that case: either the edge cover is one connected component then as you said it's made of one tree so it's forest; or it's made up of multiple tree then it's also a forest $\endgroup$ – Yos Jan 25 '18 at 13:57
  • $\begingroup$ The point is that an edge cover doesn't have to be a forest at all. The nontrivial part is proving that every component of a minimal cover is a tree. But you proposed "It could be a tree" as a counterexample to the proposition that it's always a forest. I've explained why that's not a counterexample. $\endgroup$ – David Richerby Jan 25 '18 at 15:16
  • 1
    $\begingroup$ @Yos Because if it wasn't a tree, it wouldn't be minimal. Edited. $\endgroup$ – David Richerby Jan 25 '18 at 18:49

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.