finds an edge cover of the graph g with a minimum number of edges.


uses rules vw to specify the graph g.


  • An edge cover is a set of edges that is incident to every vertex.
  • FindEdgeCover returns a list of edges.
  • FindEdgeCover will return an empty list if no edge cover is found.
  • FindEdgeCover works with undirected graphs, directed graphs, weighted graphs, multigraphs, and mixed graphs.

Background & Context

  • FindEdgeCover finds a single minimum edge cover of a graph and returns the result as an edge list. Here, an edge cover is a set of edges for which at least one edge endpoint is incident to every vertex in a graph. A minimum edge cover is an edge cover having the smallest possible number of edges. Minimum edge covers have applications in social networks, biology, and social sciences.
  • The size of (i.e. the number of edges in) a minimum edge cover of a graph is known as its edge cover number and is denoted . An edge cover can be found in polynomial time.
  • EdgeCoverQ can be used to test if a given edge set is a (not necessarily minimum) edge cover. Application of EdgeCoverQ to all possible edge subsets of a graph can therefore be used to enumerate all edge covers, and application to subsets of size equal to the edge cover number can be used to enumerate all minimum edge covers. FindVertexCover applies the same concept to vertices.


open all close all

Basic Examples  (1)

Find an edge cover:

Click for copyable input
Click for copyable input

Show the cover:

Click for copyable input

Scope  (8)

Properties & Relations  (5)

Introduced in 2010
Updated in 2015