TOPICS

# Minimum Edge Cover

A minimum edge cover is an edge cover having the smallest possible number of edges for a given graph. The size of a minimum edge cover of a graph is known as the edge cover number of and is denoted .

Every minimum edge cover is a minimal edge cover (i.e., not a proper subset of any other edge cover), but not necessarily vice versa.

Only graphs with no isolated points have an edge cover (and therefore a minimum edge cover).

A minimum edge cover of a graph can be computed in the Wolfram Language with FindEdgeCover[g]. There is currently no Wolfram Language function to compute all minimum edge covers of a graph.

If a graph has no isolated points, then

where is the matching number and is the vertex count of (Gallai 1959, West 2000).

Edge Cover, Minimal Edge Cover

## Explore with Wolfram|Alpha

More things to try:

## References

Gallai, T. "Über extreme Punkt- und Kantenmengen." Ann. Univ. Sci. Budapest, Eőtvős Sect. Math. 2, 133-138, 1959.Pemmaraju, S. and Skiena, S. Computational Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Cambridge, England: Cambridge University Press, p. 318, 2003.Skiena, S. Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, p. 178, 1990.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, 2000.

## Cite this as:

Weisstein, Eric W. "Minimum Edge Cover." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/MinimumEdgeCover.html