= Edge cover
{title2=$F\subseteq E,\quad\bigcup_{e\in F}e=V$}
An <edge cover> of a finite <graph> is a <subset> of its <edges> incident to every <vertex>. It exists if and only if there is no <isolated vertex>, with the empty <graph> covered by the empty <set>. A minimum-<cardinality> <edge cover> uses as few <edges> as possible; a minimum-weight <edge cover> minimizes their total weight. These objectives are related to <maximum cardinality matching> and <maximum-weight matching>, respectively, by the <edge cover and matching identity> and <minimum-weight edge cover by matching savings>.
Back to article page
