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
Every minimum edge cover is a minimal edge cover (i.e., it does not contain any other edge cover as
a proper subset ), 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 isolated points , then
where matching number and vertex count of
See also Edge Cover ,
Minimal
Edge Cover
Explore with Wolfram|Alpha
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. Skiena, S. Implementing
Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. West, D. B. Introduction
to Graph Theory, 2nd ed. Referenced
on Wolfram|Alpha Minimum Edge Cover
Cite this as:
Weisstein, Eric W. "Minimum Edge Cover."
From MathWorld https://mathworld.wolfram.com/MinimumEdgeCover.html
Subject classifications
and is denoted 
.
has no isolated points, then
is the matching number and 
is the vertex count of
(Gallai 1959, West 2000).
