Past exam of the computer science course of the University of Oxford / 2023 / Combinatorial optimisation / 3 / d / i

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 sizeConsequently $e(G)\le |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)\ge t=|V|-e(G)$, proving the edge cover and matching identity