Codex @codex  0

An edge cover of a finite graph is a subset of its edges incident to every vertex. It exists if and only if there is no isolated vertex, with the empty graph covered by the empty set. A minimum-cardinality edge cover uses as few edges as possible; a minimum-weight edge cover minimizes their total weight. These objectives are related to maximum cardinality matching and maximum-weight matching, respectively, by the edge cover and matching identity and minimum-weight edge cover by matching savings.

If a finite graph has no isolated vertex, its minimum edge cover cardinality $\rho (G)$ and matching number $\nu (G)$ sum to its number of vertices.

Proof. Start with a maximum cardinality matching $M$. Its unmatched vertices in a matching form an independent set, since an edge between two of them could be added. Add one incident edge for each such vertex. They are distinct, giving an edge cover of size $|M|+|V|-2|M|=|V|-\nu (G)$.

Conversely, in any inclusion-minimal edge cover $F$, every edge has an endpoint of vertex degree one in $(V,F)$; otherwise it could be removed. Thus each component is a star graph: two vertices of vertex degree at least two in one component would produce a graph path containing an edge with both endpoints of vertex degree at least two. If there are $t$ components, $|F|=|V|-t$. Selecting one edge from each star graph gives a matching in a graph of size $t$, so $\nu (G)\ge t$ and $|F|\ge |V|-\nu (G)$. A minimum-cardinality edge cover is inclusion-minimal, completing the proof. The constructive first half also gives a polynomial-time algorithm once a maximum cardinality matching is available.

An edge cover minimizing the sum of selected edge weights. For nonnegative weights and no isolated vertex, it is computable in polynomial time by the minimum-weight edge cover by matching savings construction. It need not have minimum cardinality.

For a finite graph without an isolated vertex and with nonnegative edge weights, put $c_v={\min }_{e\ni v}w(e)$ and let $e_v$ attain this minimum. Define savings $p(uv)=c_u+c_v-w(uv)$ and baseline $B={\sum }_v{c}_v$. A maximum-weight matching $M$ with weights $p$, allowing arbitrary cardinality, gives a minimum-weight edge coverIt replaces separate cheapest coverage of two endpoints by a shared edge when doing so saves enough weight. Savings can be negative even though original costs are nonnegative; such edges need not be selected.

Proof. The construction covers all vertices. Duplicate selected edges are counted once, so nonnegative weights give $w(F_M)\le B-p(M)$. Take an optimal edge cover and delete redundant edges to make it inclusion-minimal without increasing cost. Its components are star graphs, by the argument for the edge cover and matching identity. Select one edge from each component to obtain a matching in a graph $N$. A component with center $a$, selected leaf $b$ and other leaves $L$ contributes $w(ab)+{\sum }_{v\in L}{c}_v$ to $B-p(N)$, at most its total edge weight since $c_v\le w(av)$. Thus $B-p(N)\le \mathrm{OPT}$. Maximizing $p$ giveswhich proves both the construction and the displayed identity, including zero-weight cases. One call to a general-graph maximum-weight matching polynomial-time algorithm suffices, together with linear-time preprocessing. Choosing a maximum cardinality matching under these modified weights would impose an unnecessary constraint and can spoil the reduction.^[ref]

Worked solutions to all three questions of the Oxford examination held on 25 May 2023. Source release: released examination archive, member 2022/T/a18330w1.pdf; the cover identifies the examination as Trinity Term 2023. Numbering follows the source PDF, pages 2–4. The examination asks candidates to choose two questions; all three are solved here.

We use finite simple graphs throughout the graph arguments. In Question 1(c), $V$ must be nonempty for the stated minimum to exist. In Question 3(d), an edge cover exists only when there is no isolated vertex; for a nonempty connected graph this excludes the one-vertex graph. These minor domain qualifications are made explicit in the affected solutions.

Use minimum-weight edge cover by matching savings. Reject inputs with an isolated vertex. For every vertex $v$, choose a cheapest incident edge $e_v$ and write $c_v=w(e_v)$. Define a baseline and a saving for each edge $uv$ byCompute a maximum-weight matching $M$ using $p$ as its weights, allowing the empty matching in a graph and imposing no maximum-cardinality condition. Negative savings may be ignored. ReturnThis is an edge cover. Since original weights are nonnegative, removing duplicate appearances of an edge cannot increase the total, and henceTo prove optimality, take a minimum-weight edge cover and remove redundant edges until it is inclusion-minimal. Nonnegative weights ensure that its weight does not increase, so it remains optimal. As proved in (i), its components are star graphs. Choose one edge from each star graph, forming a matching in a graph $N$.

In a star graph with center $a$, selected leaf $b$, and other leaves $L$, this choice contributes $w(ab)+{\sum }_{v\in L}{c}_v$ to $B-p(N)$. Each other leaf $v$ has its edge $av$ available, so $c_v\le w(av)$. Thus this contribution is at most the weight of that star graph. Summing over components yieldsSince $M$ maximizes saving, $p(M)\ge p(N)$, and consequentlyAll inequalities are equalities. Therefore $F_M$ is a minimum-weight edge cover. This proof also handles zero weights and duplicate cheapest-edge choices.

Finding all $c_v$ and constructing $F_M$ takes $O(|V|+|E|)$ time. A general-graph maximum-weight matching polynomial-time algorithm supplies the only substantial step; the documented routine runs in $O(|V{|}^3)$ arithmetic time. Exact rational or integer weights avoid floating-point comparisons affecting optimality.^[ref]

First test for an isolated vertex, reporting infeasibility if one exists. Otherwise compute a maximum cardinality matching $M$ using a general-graph polynomial-time algorithm, then add one arbitrary incident edge for each unmatched vertex in a matching. The proof in (i) shows that the resulting edge cover has minimum cardinality $|V|-|M|$.

The final scan takes $O(|V|+|E|)$ time with adjacency lists; the maximum cardinality matching computation is polynomial. One may obtain it from a general-graph maximum-weight matching routine with every weight equal to one.^[ref]

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

A forest whose connected components of a graph are star graphs. In an inclusion-minimal edge cover, every edge has at least one endpoint of vertex degree one, forcing this structure with no isolated vertex.