$\alpha^{'}(G)\geq\frac{n}{1+\Delta(G)}$ Let $G$ be a connected graph of order $n$ and $\alpha^{'}(G)$ be the edge independence number(or matching number). Can you help me prove the inequality $\alpha^{'}(G)\geq\frac{n}{1+\Delta(G)}$ where $\Delta(G)$ is the maximum vertex degree?
 A: The answer by Adam Lowrance proves the following two theorems:
Tree Theorem. If $G$ is a tree with $n$ vertices, $n\ge2,$ then
$$\alpha'(G)\ge\frac n{\Delta(G)+1}.$$
General Theorem. If $G$ be a connected graph with $n$ vertices, $n\ge2,$ then
$$\alpha'(G)\ge\frac n{\Delta(G)+1}.$$
Here is a short proof of the Tree Theorem. Let $e(G)=|E(G)|$ be the size of $G,$ and let $\chi'(G)$ be the edge chromatic number of $G.$ If $G$ is a tree, then we have $e(G)=n-1\ge\Delta(G)$ and $\chi'(G)=\Delta(G),$ whence
$$\alpha'(G)\ge\frac{e(G)}{\chi'(G)}=\frac{n-1}{\Delta(G)}\ge\frac n{\Delta(G)+1}.$$
Here is a short proof of the General Theorem using Vizing's theorem. Without loss of generality, we may assume that $G$ is a simple graph; moreover, we may assume that $G$ is not a tree. By Vizing's theorem, $\chi'(G)\le\Delta(G)+1.$ Therefore, since $G$ is not a tree, $e(G)\ge n$ and
$$\alpha'(G)\ge\frac{e(G)}{\chi'(G)}\ge\frac n{\Delta(G)+1}.$$
Alternatively (without Vizing's theorem), let $T$ be a spanning tree in $G;$ then
$$\alpha'(G)\ge\alpha'(T)\ge\frac n{\Delta(T)+1}\ge\frac n{\Delta(G)+1}.$$
Corollary. If $G$ is a graph with $n$ vertices, and if each connected compenent of $G$ has at least $2$ vertices, then
$$\alpha'(G)\ge\frac n{\Delta(G)+1}.$$
Proof. Let $G_1,G_2,\dots,G_k$ be the components of $G$; suppose $G_i$ has $n_i$ vertices, $\alpha'(G_i)=\alpha'_i$, and $\Delta(G_i)=\Delta_i$. Then
$$\alpha'(G)=\sum_{i=1}^k\alpha'_i\ge\sum_{i=1}^k\frac{n_i}{1+\Delta_i}\ge\sum_{i=1}^k\frac{n_i}{1+\Delta(G)}=\frac n{1+\Delta(G)}$$
A: If $G$ is a single vertex, then $\alpha'(G) = 0$ and $\frac{n}{1+\Delta(G)}=1$. This is a counterexample to your inequality, but let's ignore it and prove the statement for the case that $G$ contains at least one edge.
The strategy is to prove the statement via induction on the number of edges. The base case of the induction will be when $G$ is a tree. The proof I've come up with for trees uses Berge's Lemma, and so we begin by setting up and stating that lemma.
Let $G=(V,E)$ be a connected simple graph with $n$ vertices. A matching $M$ is a collection of edges such that no vertex of $G$ is incident to more than one edge in $M$. A vertex that is incident to an edge in $M$ is said to be covered by $M$. An augmenting path of $M$ is a path in $G$ such that the starting and ending vertices are not covered by $M$.
Berge's Lemma. A matching $M$ in $G$ contains the largest possible number of edges (i.e. contains $\alpha'(G)$ edges) if and only if the matching $M$ has no augmenting paths.
Tree Theorem. Let $G$ be a tree with $n$ vertices and at least one edge. Then
$$\alpha'(G) \geq \frac{n}{1+\Delta(G)}.$$
Proof. We proceed by induction. Our base cases are when $G$ is a tree containing no paths of length 3 or greater. In these cases, $G$ is a star graph (where I am considering a path of length 1 or 2 as a star). For a star graph, we have $\alpha'(G)=1$ and $\Delta(G) = n-1$. Thus 
$$\alpha'(G) = 1 = \frac{n}{n}=\frac{n}{1+\Delta(G)}.$$
Let $G$ be a tree that contains a path of length 3 or more. Let $M$ be a matching of $G$ containing the largest possible number of edges. Thus $|M|=\alpha'(G)$. Let $P$ be a path in $G$ of length at least 3 that starts and ends at leaves of $G$. By Berge's Lemma, since $M$ is a maximum matching, at least one of the edges incident to the ends of $P$ must be in $M$ (otherwise $P$ is an augmenting path of $M$). Because $M$ is a matching, no two consecutive edges of $P$ can be in $M$. Therefore there is an edge $e$ of $P$ not incident to a leaf of $G$ such that $e\notin M$.
Deleting $e$ from $G$ yields the graph $G-e$ which is the disjoint union of two trees $G_1$ and $G_2$. Since $e$ is not incident to a leaf in $G$, both trees $G_1$ and $G_2$ contain edges. Suppose that $G_1$ has $n_1$ vertices, and $G_2$ has $n_2$ vertices. By the inductive hypothesis, we have that
$$\alpha'(G_1) \geq \frac{n_1}{1+\Delta(G_1)} ~~ \text{and} ~~ \alpha'(G_2)\geq \frac{n_2}{1+\Delta(G_2)}.$$
The total number of vertices in $G-e$ is still $n$, and so $n_1+n_2=n$. Also, the maximum degree of any vertex in $G-e$ satisfies
$$\Delta(G) -1 \leq \Delta(G-e) \leq \Delta(G).$$
Without loss of generality, assume that $\Delta(G_1)\leq\Delta(G_2)$. Since $\Delta(G-e) = \max\{\Delta(G_1),\Delta(G_2)\}$, it follows that
$$\Delta(G)-1 \leq \Delta(G_2) \leq \Delta(G).$$
Let $E_1$ and $E_2$ be the edge sets of $G_1$ and $G_2$ respectively, and define $M_1=M\cap E_1$ and $M_2=M\cap E_2$. Since $e\notin M$, it follows that $|M_1| + |M_2|=|M|=\alpha'(G)$. Also, $\alpha'(G_1)=|M_1|$ and $\alpha'(G_2)=|M_2|$ because otherwise we could construct a matching on $G$ with more than $|M|=\alpha'(G)$ edges. Therefore $\alpha'(G) = \alpha'(G_1) + \alpha'(G_2)$.
So we have
\begin{align*}
\alpha'(G) = & \; \alpha'(G_1) + \alpha'(G_2)\\
\geq & \; \frac{n_1}{1+\Delta(G_1)} + \frac{n_2}{1+\Delta(G_2)}\\
\geq & \; \frac{n_1}{1+\Delta(G_2)} + \frac{n_2}{1+\Delta(G_2)}\\
= &\; \frac{n}{1+\Delta(G_2)}\\
\geq & \; \frac{n}{1+\Delta(G)}.
\end{align*}
$$\tag*{$\blacksquare$}$$
We can use the Tree Theorem as the base case for our more general result.
General Theorem. Let $G$ be a connected graph with $n$ vertices and at least one edge. Then
$$\alpha'(G) \geq \frac{n}{1+\Delta(G)}.$$
Proof. If $G$ is a tree, then we are done by the Tree Theorem. So suppose that $G$ is not a tree, and let $M$ be a matching with $|M|=\alpha'(G)$. Since $G$ is connected and not a tree, $G$ contains a cycle as a subgraph. There is an edge $e$ in that cycle such that $e\notin M$. Since $e$ is contained in a cycle the deletion $G-e$ of $e$ from $G$ remains connected.
Since $M$ is also a matching in $G-e$, we have that $\alpha'(G)= \alpha'(G-e)$. Deleting $e$ from $G$ can reduce the maximum degree by at most one, and hence
$$\Delta(G) - 1 \leq \Delta(G-e) \leq \Delta(G).$$
Since $G-e$ also has $n$ vertices, the inductive hypothesis yields
$$\alpha'(G-e) \geq \frac{n}{1+\Delta(G-e)}.$$
Therefore
$$\alpha'(G) = \alpha'(G-e) \geq \frac{n}{1+\Delta(G-e)} \geq \frac{n}{1+\Delta(G)}.$$
$$\tag*{$\blacksquare$}$$
