Graph Theory – Sum of Minimum Edge Cover and Maximum Matching

Question

Given a connected graph, how can we prove that the number of edge of its minimum edge cover plus its maximum matching is equal to the number of vertices?

Answer 1

Given a graph $G$, let $\rho^*$ and $m^*$ denote the minimum edge cover and the maximum matching of $G$ respectively. We prove $|\rho^*| + |m^*| \leq n$ and $|\rho^*| + |m^*| \geq n$ in order below, where $n$ is the # of vertices in $G$.

• $|\rho^*| + |m^*| \leq n$

Let $S$ be the set of vertices that are not contained in $m^*$. It is easy to see that $S$ is an independent set of $G$; otherwise, we can further enlarge $m^*$, contradicting the fact that $m^*$ is a max matching. We construct an edge cover $\rho'$ of $G$ by adding one of $v$'s adjacent edges to $\rho'$ for each $v \in S$ and adding all edges in $m^*$ to $\rho'$. The resulting $\rho'$ would cover all vertices in $G$ and $|\rho'| = |m^*| + |S|$. Therefore, $$ |m^*| + |\rho^*| \leq |m^*| + |\rho'| = 2|m^*| + |S| = n \tag{$\spadesuit$} $$

• $|\rho^*| + |m^*| \geq n$

If $\rho^*$ is a minimum edge cover, then the edges in $\rho^*$ do not contain a path of length of more than $2$. This is because if a path of length of $>2$ exists, we can remove one of intermediate edges to shrink $\rho^*$, which is a contradiction. Therefore, the connected components of $\rho^*$ are all star graphs. Denote the # of connected components in $\rho^*$ as $c$ and the components as $C_1, C_2, \cdots, C_c$. We have $$ |V(C_1)| + |V(C_2)| + \cdots + |V(C_c)| = n $$ and $$ |E(C_1)| + |E(C_2)| + \cdots + |E(C_c)| = |\rho^*| $$ For a star graph, the # of edges is always $1$ less than the # of vertices; i.e., $|E(C_i)| = |V(C_i)| - 1$. Therefore, $$ |\rho^*| + c = n $$ and thus $$ |\rho^*| + |m^*| \geq |\rho^*| + c = n \tag{$\clubsuit$} $$ Combinging $(\spadesuit)$ and $(\clubsuit)$, we obtain $$ |\rho^*| + |m^*| = n $$