What an Edge Cover Covers
A vertex cover and an edge cover are both ways to describe coverage in a graph, but they cover different objects. A vertex cover is a set of vertices that meets every edge. An edge cover is a set of edges that reaches every vertex. Keeping track of which set is chosen, and what it must cover, prevents a common mix-up.
Throughout, graphs are finite and simple. For a graph \(G=(V,E)\), the degree of a vertex is the number of edges incident with it. A vertex of degree zero is isolated. The empty graph, with \(V=\varnothing\), has no isolated vertices: there are no vertices that could be isolated.
The two definitions exchange the roles of vertices and edges. For an edge cover, the chosen objects are edges and the requirement is about every vertex. For a vertex cover, the chosen objects are vertices and the requirement is about every edge. The set \(F\) need not include every edge of the graph; it must only include enough edges to reach all its vertices.
Edge Covers Work Component by Component
A connected component is a maximal set of vertices in which every pair is joined by a path. No edge joins vertices in different components. This means coverage can be checked separately in each component.
Proof. Suppose first that \(F\) is an edge cover of \(G\). Each vertex \(v\) in a component \(C\) is incident with an edge \(e\in F\). The other endpoint of \(e\) is connected to \(v\), so it belongs to the same component \(C\). Thus the edges of \(F\) in \(C\) reach every vertex of \(C\). Conversely, suppose the edges of \(F\) in each component reach every vertex of that component. Each vertex belongs to a component, so it is incident with an edge of \(F\). Hence \(F\) is an edge cover of \(G\). If \(V=\varnothing\), there are no components and no vertices to cover, so \(F=\varnothing\) satisfies the definition. \(\square\)
This componentwise view does not require the graph to be connected. It also shows why an isolated vertex is decisive: its component has one vertex and no edge available to reach it.
The Isolated-Vertex Criterion
Proof. First suppose \(G\) has an edge cover \(F\). By definition, every vertex is incident with an edge of \(F\), and therefore with an edge of \(G\). No vertex is isolated.
Conversely, suppose \(G\) has no isolated vertices. For each vertex \(v\), choose one edge \(e_v\) incident with \(v\), and let \(F=\{e_v:v\in V\}\). This is a subset of \(E\); if two vertices lead us to choose the same edge, that edge occurs only once in the set. Every vertex \(v\) is incident with its chosen edge \(e_v\), so \(F\) is an edge cover. If \(V=\varnothing\), there are no choices to make and \(F=\varnothing\), which covers every vertex vacuously. Thus an edge cover exists in this case as well. Both directions prove the criterion. \(\square\)
The construction gives a direct way to build an edge cover: choose an incident edge for each vertex, then take the union of the chosen edges. The theorem concerns existence, not the size of a smallest edge cover. In particular, choosing an edge for each vertex can select the same edge twice during the process, but the final set includes it just once.
Worked Example: An Edge Cover and a Vertex Cover
Let \(G=(V,E)\) have \(V=\{1,2,3,4,5\}\) and \(E=\{12,23,34,45\}\). Consider \(F=\{12,34,45\}\). Check whether \(F\) is an edge cover.
List the endpoints of each selected edge: \(12\) reaches \(1,2\); \(34\) reaches \(3,4\); and \(45\) reaches \(4,5\). Thus the vertices reached are \(\{1,2\}\cup\{3,4\}\cup\{4,5\}=\{1,2,3,4,5\}=V\). So \(F\) is an edge cover.
Now consider \(S=\{2,4\}\), a set of vertices. The edge \(12\) has endpoint \(2\) in \(S\), \(23\) has endpoint \(2\), \(34\) has endpoint \(4\), and \(45\) has endpoint \(4\). So \(S\) is a vertex cover. The two checks have different targets: \(F\) reaches every vertex, while \(S\) meets every edge.
Check: The degrees in the subgraph with vertex set \(V\) and edge set \(F\) are \(1,1,1,2,1\), respectively. Each is at least \(1\), confirming directly that no vertex is left uncovered by \(F\).
Worked Example: Coverage in Disconnected Components
Let \(G=(V,E)\) have \(V=\{a,b,c,d,e\}\) and \(E=\{ab,bc,ca,de\}\). The graph has two components: the triangle on \(\{a,b,c\}\) and the single edge on \(\{d,e\}\). Take \(F=\{ab,ca,de\}\).
In the triangle component, \(ab\) reaches \(a,b\), and \(ca\) reaches \(c,a\); together they reach \(\{a,b,c\}\). In the other component, \(de\) reaches both \(d\) and \(e\). Therefore \(F\) reaches all five vertices and is an edge cover.
The degree counts using just \(F\) are \(2\) for \(a\), \(1\) for \(b\), \(1\) for \(c\), \(1\) for \(d\), and \(1\) for \(e\). Every count is positive. The example also illustrates the componentwise lemma: coverage in one component cannot substitute for coverage in another, but each component can be checked on its own.
Check: The listed edges in \(F\) account for every vertex: \(a,b\) occur in \(ab\), \(c\) occurs in \(ca\), and \(d,e\) occur in \(de\). No vertex is omitted.
Worked Example: An Isolated Vertex Blocks an Edge Cover
Let \(G=(V,E)\) have \(V=\{p,q,r,s\}\) and \(E=\{pq,qr\}\). The vertex \(s\) appears in no edge, so its degree is \(0\). The available edges \(pq\) and \(qr\) reach only the vertices in \(\{p,q,r\}\). No subset of \(E\) can reach \(s\); consequently \(G\) has no edge cover.
In contrast, \(\{q\}\) is a vertex cover: \(q\) is an endpoint of \(pq\), and it is also an endpoint of \(qr\). Thus this graph has a vertex cover even though it has no edge cover. Having one kind of cover does not guarantee having the other.
Check: The full edge list contains \(p\), \(q\), and \(r\) as endpoints, but not \(s\). The obstruction is not a poor choice of edges; there simply is no edge incident with \(s\) to choose.
Common Mix-Ups and Why the Criterion Helps
Mistake: calling a vertex cover an edge cover. In the last example, the calculation “\(q\) meets both edges, so \(\{q\}\) is an edge cover” is wrong. It checks that every edge has an endpoint in the chosen set, which is precisely the vertex-cover condition. To test an edge cover, the chosen set must consist of edges and every vertex must appear as an endpoint of one of them. Here \(\{q\}\subseteq V\), and \(s\) cannot be reached by any edge set.
Mistake: assuming a disconnected graph cannot have an edge cover. Disconnectedness alone is not an obstruction. The second example has two components and an edge cover because every vertex in each component has an incident edge. The relevant obstruction is an isolated vertex, not the number of components.
The criterion is useful before attempting to construct or analyze edge covers: inspect whether any vertex has degree zero. If one does, no edge cover exists. If none does, choosing one incident edge at each vertex proves existence immediately. For the empty graph, the definition is vacuously satisfied by the empty edge set; this is consistent with the theorem because it has no isolated vertices.
Check Your Understanding
For each question, distinguish carefully between the selected set of vertices and the selected set of edges.
- Let \(V=\{1,2,3,4\}\) and \(E=\{12,23,34\}\). Is \(\{12,34\}\) an edge cover? Verify by listing which vertices each selected edge reaches.
- Give an example of a graph with two components that has an edge cover, and verify coverage separately in each component.
- Prove that a graph with an isolated vertex has no edge cover, even if all its other vertices are covered by selected edges.
- Does the graph with \(V=\varnothing\) and \(E=\varnothing\) have an edge cover? Explain using the definition.
- For \(V=\{a,b,c\}\) and \(E=\{ab,bc\}\), identify a vertex cover and explain why that set is not itself an edge cover.