# Chapter 62. Edge Covers

# 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](https://en.wikipedia.org/wiki/Edge_cover?utm_source=chatgpt.com))

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:

1. Start with a matching.
2. 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](https://en.wikipedia.org/wiki/Edge_cover?utm_source=chatgpt.com))

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

1. Compute a maximum matching \(M\).
2. Every unmatched vertex is uncovered.
3. Add one incident edge for each uncovered vertex.

The resulting edge set is a minimum edge cover.

### Size

If

$$
|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

1. Find a maximum matching.
2. 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|\) | Gallai identity |
| 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

1. Find a minimum edge cover of \(P_6\).

2. Compute \(\rho(C_7)\).

3. Prove that a graph with an isolated vertex has no edge cover.

4. Prove Gallai's identity.

5. Show that every perfect matching is a minimum edge cover.

6. Construct a minimum edge cover from a maximum matching.

7. Compute \(\rho(K_5)\).

8. Explain why edge cover is polynomial-time solvable.

9. Compare edge covers and vertex covers for a small graph.

10. Write the linear programming formulation for minimum edge cover.