Prove that every graph G without isolated vertices has a matching of size at least ${n(G)\over 1+∆(G)}$. (Hint: Apply induction on $e(G)$).
I know that a perfect matching is the size of a minimum edge cover, but I don't really think that relates to this problem. I have no idea where to go with it.
On
From any graph $G$ without isolated vertices arbitrarily remove non-pendant edges (degrees of both incident vertices at least $2$) one at a time until no more edges can be removed like this. The resulting graph $H$ must be a disjoint union of stars $K_{1,k}$, $k\ge1$:
Suppose $H=\bigsqcup_{i=1}^nK_{1,d_i}$; it is easy to see that $\max_id_i=\Delta(H)$ and $$\nu(H)=n=\sum_{i=1}^n\frac{1+d_i}{1+d_i}\ge\sum_{i=1}^n\frac{1+d_i}{1+\Delta(H)}=\frac{|V(H)|}{1+\Delta(H)}$$ Now reverse the edge removal sequence, adding edges to $H$ to get $G$. The number of vertices never changes since each edge removed was non-pendant, so did not leave an isolated vertex, yet the matching number and maximum degree never decrease, so the inequality is always preserved. Hence $\nu(G)\ge\frac{|V(G)|}{1+\Delta(G)}$ holds for arbitrary graphs $G$.
Hint: Do exactly as the hint says!
As a base case, you need to consider, say, any graph $G$ without isolated vertices which has $e(G)=1$. Of course, there's only one such graph; it has $n(G)=2$ and $\Delta(G)=1$, and its single edge is certainly a matching of size at least $\frac{2}{1+1}=1$.
Now, suppose that all graphs with $e(G)\leq k$ satisfy the desired property, and suppose $G$ is a graph with $e(G)=k+1$. Pick a vertex $v$ of maximum degree, and pick one of its edges $e_0$. Consider three cases here:
Case 1: Removing $e_0$ isolates both of its endpoints. In this case, it must be true that $\Delta=1$ (why?); think about the graph obtained from $G$ by removing both endpoints of $e_0$, and apply the inductive hypothesis.
Case 2: Removing $e_0$ isolates one of its endpoints but not the other. In this case, it must isolate the endpoint other than $v$ (why?); try considering the graph obtained by removing this other vertex, and apply the inductive hypothesis.
Case 3: Removing $e_0$ does not isolate any vertices. Apply the inductive hypothesis directly.
Bear in mind that I haven't worked this through to the end... but, if this is true and can be proved by induction on $e(G)$, then this is really the only road map that can work!