# 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?

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

• Could you explain why is it true the inequality $|m^∗|+|ρ^∗|≤|m^∗|+|ρ′|$ while proving $|ρ^∗|+|m^∗|\leq n$? Aug 4, 2017 at 19:56
• I think i am not getting it right because for instance, at this graph you have $M^∗ = \{(0, 1), (3, 2)\}$ and $P^∗ = \{(0,1), (1,2),(2,3)\}$ and $S = M^∗$ so the inequality yields $2 + 3 \leq 2 + 2$ which is false. Aug 4, 2017 at 20:05
• @jscherman This is just because $\rho^*$ is a minimum edge cover, while $\rho'$ is some edge cover. Nov 21, 2017 at 14:21

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