Size of matching 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.
 A: 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!
A: I will prove that there is always an edge that you can remove, and add to your matching  edges without removing more than 1+∆(G) vertices from G. ( if u,v are two vertices of edge e, u,v and all isolated vertices after removing u, v and these's edges will be removed from G.)
Well first assume that there is a vertex z which has degree 1, if you remove this edge, so you have to remove z, x ( only z's neighbor) and at most all the neighbors of x, which is not more than ∆(G) (containing z). which at most is 1+∆(G).
now assume there is no vertex with degree 1, choose edge e( u, v) as much as there is no vertex with degree 1, so if a vertex is isolated after removing u and v, so it has to be connect to both, u and v. the most common neighbor u and v can have ( as much these two are connected) is ∆(G)-1 , so if we remove all these vertices,u and v it will be at most 1+∆(G). 
so if you get the proof as a constructing proof, which in each step it will chose a new edge for matching, it has been proofed that {number_of_steps >= n(G)/(1+∆(G))}.
A: 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$:

*

*Any edge in a cycle has endpoint degrees at least $2$ and can be removed; $H$ must be a forest

*If there is a path of at least $3$ edges in a tree there are at least two interior vertices, all of which have degree at least $2$. Any edge between interior vertices can be chosen for removal, so $H$ is a forest with each tree having diameter at most $2$

*The only trees with diameter at most $2$ are stars

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