Graph's Matching and edge covering Let $G$ be a graph and $M$ a match with maximum size and $F$ an edge cover with minimal size. Prove that:
$|M|+|F| = |V|$
That means that the number of all Matches with maximum size and the number of all Edge Covers with minimal size is equal to the number of vertices.
I know what this is about buuut...how do I proof it? Induction over the number of vertices?
And its not a specific graph like a Wheel or Hypercube. Its some Graph with degree > 0
 A: Let $M$ be a maximum matching. Form an edge cover $X$ as follows. First, place all edges of $M$ into $X$. Next, for each vertex $v$ not incident to an edge of $M$, choose any edge that is incident to $v$ and put that edge in $X$. Since there are $|V|-2|M|$ vertices not incident to an edge of $M$, $X$ has $|M|+(|V|-2|M|)= |V|-|M|$ edges. Hence, if $F$ is a minimum edge cover, we have $$|F|\leq |X|=|V|-|M|$$ and so $|F|+|M|\leq |V|$.
Now let $F$ be a minimum edge cover. Notice that if $e=uv\in F$, then at least one of $u$ or $v$ cannot be incident to any other edge in $F$ since if both were, then we could remove $e$ from $F$ to get a smaller edge cover. So the edges of $F$ induce a subgraph that is a disjoint collection of stars. If there are $k$ stars, then we have $|V|=k+|F|$. On the other hand, if we choose an edge from each star, we get a matching of size $k$. Hence $$|V|-|F| = k \leq |M|,$$ and so $|V|\leq |M|+|F|.$ 
A: Let $\nu(G)$ denote the maximum size of a matching in $G=(V,E)$ and $\rho(G)$ the minimum number of edges needed to cover all vertices of $G$.  We want to show that $\nu(G)+\rho(G)=|V|$.  Note that we need to assume that $G$ has no isolated vertices, for otherwise $G$ does not contain a set of edges covering all vertices.
Let $M \subseteq E$ be a maximum matching of $G$.  The edges in $M$ cover $2|M|$ vertices.  Each of the remaining $|V|-2|M|$ vertices has degree at least $1$ and so can be covered by some edge.  Hence, $G$ has an edge covering of cardinality $|M| + (|V|-2|M|) = |V|-|M|$.  This implies that the size of a minimum edge cover is $\rho(G) \le |V|-|M|$.  Since $|M|=\nu(G)$, we have shown that $\nu(G) + \rho(G) \le |V|$.
To prove the reverse inequality, let $F \subseteq E$ be a minimum edge cover of $G$.  Observe that the subgraph $(V,F)$ contains no isolated vertices because $F$ is an edge cover.  Each connected component of the subgraph $(V,F)$ is a star, ie, is isomorphic to $K_{1,r}$ for some $r \ge 1$. To see why, suppose some vertex $x$ in one of the connected components has degree $> 1$.  If each neighbor of $x$ has degree $1$ in $(V,F)$, then we are done.  Otherwise, some neighbor $y$ of $x$ has degree at least $2$.  So $(V,F)$ contains a walk of length 3 of the form $a,x,y,a$ or $a,x,y,b$, and the middle edge of this walk can be removed to give a smaller edge cover, contradicting the minimality of $|F|$. 
We showed that $(V,F)$ is a vertex-disjoint union of stars. The number of edges in a star $K_{1,r}$ is $r-1$.  If $(V,F)$ consists of $\ell$ stars, then the number of edges in $(V,F)$ is $|F|=|V|-\ell$.  Hence $\ell = |V|-|F|$.  Since $(V,F)$ is the vertex-disjoint union of $\ell$ stars and each star can contribute one edge to a matching, the maximum size of a matching is $\nu(G) \ge \ell$.  Hence, $\nu(G) \ge |V|-|F| = |V| - \rho(G)$. This proves that $\nu(G) + \rho(G) \ge |V|$.
