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? 
 A: 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:

*

*Removing the $k$ edges of $M \cap P$

*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)

*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 $G$ 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'
$$
A: 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
$$
