# How to prove that a minimum edge cover is a forest?

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.

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