Prove that the sum of minimum edge cover and maximum matching is the vertex count

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?

Solution 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 $$

Solution 2:

I'm proposing an alternative proof, which may offer some new perspectives.

We traditionally denote the number of vertices by $n$, the edge covering number by $\beta'$, and the matching number by $\alpha'$. The goal is to prove the identity:

Theorem: for any graph $G$ without isolated vertices: $\alpha' + \beta' = n$

We'll use the following lemma:

Lemma: any minimum edge covering contains a maximum matching.

Note: the Lemma doesn't come out of nowhere - it's suggested by the theorem we try to prove. Indeed, viewed as a spanning subgraph of $G$, a minimum edge covering has the same $n$ and $\beta'$ as $G$, and would therefore have the same $\alpha'$.

Proof of the Lemma: Let $F$ a minimum edge covering of a graph $G$ (thus $|F| = \beta'$), $H$ the spanning subgraph of $G$ with edge set $F$, and $M$ a maximum matching of $H$ (thus also a matching of $G$).

Observe that $H$ has a very constrained edge structure: any edge of $H$ is either in $M$, or joins a matched vertex $s$ to an unmatched vertext $u$ (and is the only edge incident to $u$). Indeed, an edge $e \in F \setminus M$ cannot join two matched vertices (as $F$ would not be a minimum edge covering) and cannot join two unmatched vertices (as $M$ would not be a maximum matching)

Assume by way of contradiction that $M$ is not a maximum matching of $G$. By Berge's Lemma, $G$ has an $M$-augmenting path $P$, of odd length $2k + 1$. We construct a new edge covering $F'$ from $F$, by:

1. Removing the $k$ edges of $M \cap P$
2. Removing the 2 edges covering the ends of $P$ (as observed above, since the ends of $P$ are unmatched by $M$, each one is covered by exactly one edge joining it to a matched vertex)
3. Adding at most $k + 1$ edges from $P \setminus M$ (those edges which are not already in $F. This covers any vertex which may have been uncovered by the previous removals.

$F'$ is an edge covering with $|F'| < |F|$, contradicting the choice of $F$.

Proof of the Theorem: As above, let $F$ a minimum edge covering of $G$ (thus $|F| = \beta'$), $H$ the spanning subgraph of $G$ with edge set $F$, and $M$ a maximum matching of contained in $F$ as per the Lemma (thus $|M| = \alpha'$). Let $U$ the set of unmatched vertices.

Decomposing $F$, and recalling the observation about the edge structure of $H$, we get

$$ |F| = \beta' = |M| + |F \setminus M| = |M| + |U| = \alpha' + |U| \tag{1}\label{1} $$

Decomposing the vertex set of $G$ into matched and unmatched vertices, we get:

$$ n = 2|M| + |U| = 2\alpha' + |U| \tag{2}\label{2} $$

Subtracting $\eqref{2}$ and $\eqref{1}$:

$$ \alpha' = n - \beta' $$