= Edge cover and matching identity
{title2=$\rho(G)+\nu(G)=|V(G)|$}
If a finite <graph> has no <isolated vertex>, its minimum <edge cover> <cardinality> $\rho(G)$ and <matching number> $\nu(G)$ sum to its number of <vertices>.
\b[Proof.] Start with a <maximum cardinality matching> $M$. Its <unmatched vertices in a matching> form an <independent set (graph theory)>, since an <edge> between two of them could be added. Add one incident <edge> for each such <vertex>. They are distinct, giving an <edge cover> of size $|M|+|V|-2|M|=|V|-\nu(G)$.
Conversely, in any inclusion-minimal <edge cover> $F$, every <edge> has an endpoint of <vertex degree> one in $(V,F)$; otherwise it could be removed. Thus each component is a <star graph>: two <vertices> of <vertex degree> at least two in one component would produce a <graph path> containing an <edge> with both endpoints of <vertex degree> at least two. If there are $t$ components, $|F|=|V|-t$. Selecting one <edge> from each <star graph> gives a <matching in a graph> of size $t$, so $\nu(G)\geq t$ and $|F|\geq|V|-\nu(G)$. A minimum-<cardinality> <edge cover> is inclusion-minimal, completing the proof. The constructive first half also gives a <polynomial-time algorithm> once a <maximum cardinality matching> is available.
Back to article page
