Chapter 62. Edge Covers

An edge cover is a collection of edges that touches every vertex of a graph. Edge covers are dual in spirit to vertex covers. Instead of selecting vertices to cover edges, one selects edges to cover vertices. Edge covers are closely related to matchings and form an important part of combinatorial optimization. (en.wikipedia.org)

The theory of edge covers is simpler than the theory of vertex covers, but the interaction between edge covers and matchings leads to elegant structural identities and efficient algorithms.

62.1 Definition

Let

G=(V,E)

be a graph.

An edge cover is a subset

F \subseteq E

such that every vertex of $G$ is incident with at least one edge in $F$ .

Equivalently,

\forall v \in V, \quad \exists e \in F

such that $v$ is an endpoint of $e$ .

Thus every vertex is “covered” by at least one selected edge.

For example, consider the path

v_1-v_2-v_3-v_4.

The set

F=\{v_1v_2,\; v_3v_4\}

is an edge cover, because every vertex touches one of these edges.

The set

\{v_2v_3\}

is not an edge cover, because vertices $v_1$ and $v_4$ remain uncovered.

62.2 Edge Cover Number

A minimum edge cover is an edge cover of smallest possible size.

Its size is denoted by

\rho(G).

Thus,

\rho(G) = \min\{|F| : F \text{ is an edge cover of } G\}.

The minimum edge cover problem asks for an edge cover using as few edges as possible.

62.3 Existence of Edge Covers

A graph has an edge cover if and only if it contains no isolated vertices.

Proof

Suppose $v$ is isolated.

No edge is incident with $v$ , so no edge set can cover $v$ . Hence no edge cover exists.

Conversely, suppose every vertex has degree at least one.

Then the entire edge set

E

covers every vertex.

Thus an edge cover exists.

This proves the characterization.

62.4 Edge Covers in Standard Graphs

Paths

For the path graph $P_n$ ,

\rho(P_n) = \left\lceil \frac{n}{2} \right\rceil.

Cycles

For the cycle graph $C_n$ ,

\rho(C_n) = \left\lceil \frac{n}{2} \right\rceil.

Complete Graphs

For the complete graph $K_n$ ,

\rho(K_n) = \left\lceil \frac{n}{2} \right\rceil.

Indeed, every edge covers two vertices.

Stars

For the star graph

K_{1,n},

the center edge set itself covers all vertices, so:

\rho(K_{1,n})=n.

Each leaf requires its own incident edge.

62.5 Minimal and Minimum Edge Covers

As with vertex covers, minimal and minimum mean different things.

Term	Meaning
Minimal edge cover	No edge can be removed
Minimum edge cover	Smallest possible size

Every minimum edge cover is minimal.

The converse need not hold.

62.6 Relationship with Matchings

Edge covers are strongly connected to matchings.

Suppose $M$ is a matching.

Each edge of $M$ covers two vertices.

Unmatched vertices may still remain uncovered.

To produce an edge cover:

Start with a matching.
Add one incident edge for each uncovered vertex.

This relationship leads to a fundamental identity.

62.7 Gallai’s Identity

Suppose $G$ has no isolated vertices.

Then:

\nu(G)+\rho(G)=|V|.

\nu(G)+\rho(G)=|V|

Here:

Symbol	Meaning
$\nu(G)$	Maximum matching size
$\rho(G)$	Minimum edge cover size

This theorem is called Gallai’s identity. (en.wikipedia.org)

It is one of the most elegant relations in graph theory.

62.8 Proof of Gallai’s Identity

Let $M$ be a maximum matching.

Suppose:

|M|=\nu(G).

The matching covers exactly:

2\nu(G)

vertices.

Therefore:

|V|-2\nu(G)

vertices remain uncovered.

Since $M$ is maximum, every uncovered vertex must be adjacent to some matched vertex. Otherwise, an additional matching edge could be added.

Add one incident edge for each uncovered vertex.

These additional edges cover all remaining vertices.

Thus the resulting edge cover contains:

\nu(G) + (|V|-2\nu(G)) = |V|-\nu(G)

edges.

Hence:

\rho(G)\le |V|-\nu(G).

Conversely, let $F$ be a minimum edge cover.

Every connected component of the graph formed by $F$ is either:

Component	Structure
Single edge	Covers two vertices
Star-like component	More edges than necessary

Because $F$ is minimum, each component must contain exactly one more vertex than edge.

Selecting one edge from each component produces a matching.

Counting shows:

\nu(G)\ge |V|-\rho(G).

Combining the inequalities yields:

\nu(G)+\rho(G)=|V|.

62.9 Constructing Minimum Edge Covers

Gallai’s identity gives an efficient construction method.

Algorithm

Compute a maximum matching $M$ .
Every unmatched vertex is uncovered.
Add one incident edge for each uncovered vertex.

The resulting edge set is a minimum edge cover.

Size

|M|=\nu(G),

then the number of unmatched vertices equals:

|V|-2\nu(G).

Adding one edge per uncovered vertex gives:

\nu(G)+(|V|-2\nu(G)) = |V|-\nu(G) = \rho(G).

Thus the construction is optimal.

62.10 Edge Covers and Perfect Matchings

If a graph has a perfect matching, then:

\nu(G)=\frac{|V|}{2}.

Using Gallai’s identity:

\rho(G) = |V|-\frac{|V|}{2} = \frac{|V|}{2}.

Thus every perfect matching is automatically a minimum edge cover.

Indeed, a perfect matching already covers every vertex using the fewest possible edges.

62.11 Edge Covers and Trees

Trees provide especially simple examples.

Let $T$ be a tree with $n$ vertices.

Since trees are sparse, minimum edge covers often resemble matchings with additional leaf-covering edges.

Example

Consider:

v_1-v_2-v_3-v_4-v_5.

A maximum matching has size:

2.

Hence:

\rho(T)=5-2=3.

One minimum edge cover is:

\{v_1v_2,\; v_2v_3,\; v_4v_5\}.

62.12 Edge Cover Algorithms

The minimum edge cover problem is computationally easy.

Main Strategy

Find a maximum matching.
Extend it into an edge cover.

Thus edge cover algorithms inherit the complexity of matching algorithms.

Complexity

Graph Type	Complexity
Bipartite graphs	Polynomial
General graphs	Polynomial

Unlike vertex cover, edge cover is not NP-complete.

62.13 Weighted Edge Covers

Suppose each edge has weight:

w(e).

The goal becomes minimizing:

\sum_{e \in F} w(e).

Weighted edge covers arise in network design, transportation, and infrastructure planning.

These problems can be solved using weighted matching techniques.

62.14 Edge Covers and Dominating Structures

Edge covers are related to domination concepts.

A dominating set selects vertices that dominate neighboring vertices.

An edge cover selects edges that dominate vertices through incidence.

Both problems concern efficient coverage, but the objects selected differ.

62.15 Edge Covers and Hypergraphs

In hypergraphs, an edge may contain many vertices.

An edge cover becomes a family of hyperedges whose union equals the vertex set.

This version appears in:

Area	Application
Database systems	Query optimization
Set systems	Covering problems
Combinatorial design	Block coverings

The hypergraph edge cover problem becomes substantially more difficult.

62.16 Edge Cover Polytope

Edge covers can also be described using linear inequalities.

Introduce variables:

x_e= \begin{cases} 1, & e \in F, \\ 0, & e \notin F. \end{cases}

The edge-cover constraints become:

\sum_{e \ni v} x_e \ge 1

for every vertex $v$ .

\sum_{e \ni v} x_e \ge 1

These inequalities define the edge-cover polytope.

Linear programming methods apply naturally to weighted versions.

62.17 Edge Covers and Flows

Edge cover problems can be transformed into matching or flow problems.

In bipartite graphs, minimum edge cover can be solved through maximum matching, which in turn reduces to maximum flow.

Thus edge covers are closely connected to network optimization.

62.18 Comparison with Vertex Covers

Edge covers and vertex covers solve dual-looking problems.

Problem	Selected Objects	Covered Objects
Vertex cover	Vertices	Edges
Edge cover	Edges	Vertices

Despite the similar names, the computational behavior differs greatly.

Problem	Complexity
Minimum vertex cover	NP-complete
Minimum edge cover	Polynomial

The matching connection explains much of this difference.

62.19 Applications

Edge covers appear in many practical settings.

Application	Interpretation
Sensor networks	Communication links covering devices
Transportation	Routes serving all locations
Resource allocation	Assignments touching all resources
Infrastructure design	Connectivity guarantees
Scheduling	Tasks incident with active channels

The structure naturally models coverage by pairwise relationships.

62.20 Common Identities

Identity	Meaning
(\nu(G)+\rho(G)=	V
Perfect matching $\Rightarrow$ minimum edge cover	Matching already covers all vertices
No isolated vertices $\Leftrightarrow$ edge cover exists	Existence condition

These formulas summarize the central structure of edge-cover theory.

62.21 Exercises

Find a minimum edge cover of $P_6$ .
Compute $\rho(C_7)$ .
Prove that a graph with an isolated vertex has no edge cover.
Prove Gallai’s identity.
Show that every perfect matching is a minimum edge cover.
Construct a minimum edge cover from a maximum matching.
Compute $\rho(K_5)$ .
Explain why edge cover is polynomial-time solvable.
Compare edge covers and vertex covers for a small graph.
Write the linear programming formulation for minimum edge cover.