Minimum Edge Covers and Gallai's Identity

From a Matching to an Edge Cover

A matching uses pairwise disjoint edges, while an edge cover uses edges to reach every vertex. A maximum matching may leave vertices uncovered, but in a graph with no isolated vertices each such vertex has an incident edge available. The key fact is that an unmatched vertex in a maximum matching cannot be adjacent to another unmatched vertex. This lets us add one edge for each unmatched vertex without duplicating an added edge.

All graphs here are finite and simple. A matching is a set of pairwise vertex-disjoint edges. A maximum matching is a matching of largest possible size, and $\nu(G)$ denotes that size. A matching is perfect if it covers every vertex. An edge cover is a set of edges such that every vertex is incident to at least one selected edge. A minimum edge cover is an edge cover of smallest size.

Definition: For a graph $G$ with no isolated vertices, let $\rho(G)$ denote the minimum size of an edge cover of $G$. An isolated vertex has no incident edge, so a graph with an isolated vertex has no edge cover. For the empty graph, the empty edge set is an edge cover and we set $\rho(G)=0$.

A graph with no isolated vertices has an edge cover: choose one incident edge for each vertex and take the set of chosen edges. Some choices may coincide, but the resulting set still covers every vertex. Because the graph is finite, a minimum edge cover and a maximum matching both exist.

Why the Construction Works

Lemma: If $M$ is a maximum matching, no edge joins two vertices that are both unmatched by $M$.

Proof. Suppose an edge $uv$ joined two vertices unmatched by $M$. Neither endpoint would be incident to an edge of $M$, so $M\cup\{uv\}$ would still be a matching. Its size would be $|M|+1$, contradicting that $M$ is maximum. Therefore no such edge exists. $\square$

Now take a maximum matching $M$. It covers $2\nu(G)$ vertices, so $n-2\nu(G)$ vertices are unmatched. Choose one incident edge for each unmatched vertex. The lemma ensures each chosen edge joins an unmatched vertex to a matched one. In particular, no two unmatched vertices can choose the same edge: if they did, that edge would join those two unmatched vertices. None of the chosen edges is already in $M$, since each is incident to an unmatched vertex. Thus the construction adds exactly one distinct edge per unmatched vertex.

Find a maximum matching.
Let $M$ have size $\nu(G)$. The vertices it does not cover number $n-2\nu(G)$.

Choose incident edges.
For each unmatched vertex, select any edge incident to it. Such an edge exists because there are no isolated vertices.

Take the union.
Keep all edges of $M$ and all selected edges. They cover every vertex, and the selected edges are distinct and outside $M$.

The result is an edge cover with $\nu(G)+(n-2\nu(G))=n-\nu(G)$ edges. To conclude it is minimum, we also need to show that no edge cover can be smaller.

A Lower Bound for Every Edge Cover

Lemma: If $G$ has no isolated vertices and $F$ is any edge cover of $G$, then $|F|\ge n-\nu(G)$.

Proof. If $V(G)=\varnothing$, then $F=\varnothing$, $n=0$, and $\nu(G)=0$, so the inequality holds. Otherwise consider the spanning subgraph $H=(V(G),F)$. Since $F$ covers every vertex, every component of $H$ has at least two vertices. Let $c$ be the number of components, and let component $i$ have $v_i$ vertices and $e_i$ edges. A connected graph on $v_i$ vertices has at least $v_i-1$ edges: start from one vertex and, while some vertex remains unreached, use connectedness to choose an edge from a reached vertex to an unreached one. Each step reaches a new vertex and uses a distinct edge, so reaching all $v_i$ vertices uses $v_i-1$ edges. Hence $e_i\ge v_i-1$. Summing over the components gives $|F|\ge n-c$. Choose one edge from each component of $H$. These $c$ edges form a matching in $G$, since different components have disjoint vertex sets. Therefore $c\le\nu(G)$, and so $|F|\ge n-c\ge n-\nu(G)$, as required. $\square$

Theorem (Gallai’s identity): If $G$ is a finite graph with no isolated vertices, then $$ \rho(G)+\nu(G)=n. $$

Proof. If $G$ is empty, both parameters are $0$, so the identity holds. Otherwise, the construction from a maximum matching gives an edge cover of size $n-\nu(G)$, so $\rho(G)\le n-\nu(G)$. The lower-bound lemma applied to a minimum edge cover gives $\rho(G)\ge n-\nu(G)$. Thus $\rho(G)=n-\nu(G)$, which is equivalent to the stated identity. $\square$

Worked Examples

Worked Example: A Perfect Matching

Let $G=(V,E)$, where $V=\{a,b,c,d,e,f\}$ and $E=\{ab,bc,ca,cd,de,ef,fd\}$. Take $M=\{ab,cd,ef\}$. These edges are pairwise vertex-disjoint and cover all six vertices, so $M$ is perfect.

There are no unmatched vertices, so the construction adds no edges. The resulting edge cover is $F=M$, with $|F|=3$. To check it is minimum directly, each edge covers at most two vertices. An edge cover of six vertices therefore needs at least $6/2=3$ edges. Since $F$ has exactly three edges, $\rho(G)=3$. Also, no matching can have more than $6/2=3$ edges, and $M$ has three, so $\nu(G)=3$. The identity checks numerically: $3+3=6=n$.

Worked Example: One Unmatched Vertex

Let $G=(V,E)$, where $V=\{1,2,3,4,5\}$ and $E=\{12,23,31,34,45\}$. The matching $M=\{12,45\}$ covers vertices $1,2,4,5$, leaving vertex $3$ unmatched. Since a matching on five vertices has at most $\lfloor5/2\rfloor=2$ edges, $M$ is maximum and $\nu(G)=2$.

Vertex $3$ is incident to edges $23,31,34$; choose $34$. The constructed edge cover is $F=\{12,45,34\}$. Its edges cover $1,2$, $4,5$, and $3$, respectively, so every vertex is covered. They are three distinct edges, giving $|F|=3$. Gallai’s identity gives $\rho(G)=5-2=3$, so this cover is minimum. Substitution checks the identity: $\rho(G)+\nu(G)=3+2=5=n$.

Worked Example: A Disconnected Graph

Let $G=(V,E)$, where $V=\{a,b,c,d,e,f,g\}$ and $E=\{ab,bc,ca,de,df,dg\}$. The graph has a triangle on $\{a,b,c\}$ and a star with centre $d$ and leaves $e,f,g$. In the triangle a matching has at most one edge, and in the star it has at most one edge. Thus every matching in $G$ has at most two edges. The matching $M=\{ab,de\}$ has two, so it is maximum and $\nu(G)=2$.

The unmatched vertices are $c,f,g$. Choose incident edges $ca,df,dg$, respectively. Together with $M$, they give $F=\{ab,de,ca,df,dg\}$, with five distinct edges. The triangle’s vertices are covered by $ab$ and $ca$; the star’s vertices are covered by $de,df,dg$. Thus $F$ is an edge cover. The theorem gives $\rho(G)=7-2=5$, so this cover is minimum; checking the sum gives $5+2=7=n$.

Common Pitfalls and Uses

Do not apply the construction to a nonmaximum matching. For example, let $V=\{u,v,w,x\}$ and $E=\{uv,wx\}$. If one starts with the empty matching, both $u$ and $v$ are unmatched and might each choose $uv$. The chosen set then contains just one edge, not two distinct added edges. The error is treating the empty matching as maximum: it is not, since $\{uv,wx\}$ is a matching of size two. For a maximum matching, the lemma rules out an edge between two unmatched vertices, which is exactly what guarantees distinct added edges.

Count selected edges as a set. An arbitrary edge-cover procedure may choose the same edge for both of its endpoints, so counting choices need not count distinct edges. In the maximum-matching construction, the lemma prevents this duplication among the unmatched vertices; the proof also checks that no added edge belongs to the matching already selected.

The hypothesis of no isolated vertices is essential: an isolated vertex cannot be covered by any edge, so $\rho(G)$ is not defined as a finite minimum edge-cover size for such a graph. For a graph with no isolated vertices, the identity remains useful even when the graph is disconnected: both the construction and the lower bound work across all components. In practice, a maximum matching gives not only a numerical lower bound on how many edges an edge cover needs, but also an explicit minimum edge cover once one incident edge is chosen for each unmatched vertex.

Check Your Understanding

Use the definitions and arguments above to answer the following questions.

Why can a maximum matching leave unmatched vertices only if every edge incident to one of them has its other endpoint matched?
In the construction, why are the added edges distinct from one another and from the matching edges?
Explain why choosing one edge from each component of the spanning subgraph $(V,F)$ gives a matching.
For a graph with no isolated vertices, $n=9$ and $\nu(G)=4$. What is $\rho(G)$, and how many vertices are unmatched by a maximum matching?
Why does the identity not provide a finite edge-cover size when the graph has an isolated vertex?