= Solution
Assume $G$ has no <isolated vertex>; otherwise an <edge cover> does not exist. In particular, a one-<vertex> <connected graph> is an excluded degenerate case of the statement.
Let $M$ be a <maximum cardinality matching>, of size $m(G)$, and let $U$ be its <unmatched vertices in a matching>. There is no <edge> joining two <vertices> of $U$, since adding it would enlarge $M$. Choose one incident <edge> for each $u\in U$. These chosen <edges> are distinct and outside $M$, so together they form an <edge cover> of size
$$
m(G)+|U|=m(G)+|V|-2m(G)=|V|-m(G).
$$
Consequently $e(G)\leq|V|-m(G)$.
For the opposite bound, let $F$ be a minimum-<cardinality> <edge cover>. It is inclusion-minimal. Every selected <edge> has an endpoint of <vertex degree> one in $(V,F)$: otherwise deleting that <edge> would leave both endpoints covered. Each <connected component of a graph> of $(V,F)$ is therefore a <star graph>. To see this, a component can have at most one <vertex> of <vertex degree> greater than one; a shortest <graph path> between two such <vertices> would contain an <edge> whose endpoints both have <vertex degree> greater than one. A component with no such <vertex> is a single <edge>, also a <star graph>.
If there are $t$ such <star graphs>, each has one fewer <edge> than <vertices>, so $|F|=|V|-t$. Select one <edge> from each component to get a <matching in a graph> of size $t$. Hence $m(G)\geq t=|V|-e(G)$, proving the <edge cover and matching identity>
$$
\boxed{e(G)+m(G)=|V|.}
$$
Back to article page
