The induced matching bound for graphs of maximum degree at least three

Let $G$ be a connected graph, let $u_s(G)$ denote its induced matching number, let $n(G)$ denote its number of vertices, and let $C_5^2$ and $K_{3,3}^+$ be the two exceptional graphs described in the paper: $C_5^2$ is obtained from a $5$-cycle by replacing every vertex by an independent set of order $2$, while $K_{3,3}^+$ is obtained from $K_{3,3}$ by subdividing one edge once. Let $\Delta$ be the maximum degree of $G$.

The induced matching bound. If $G\notin\{C_5^2,K_{3,3}^+\}$ and $\Delta\geq 3$, then

$$\nu_s(G) \geq \frac{1}{\left(\left\lceil\frac{\Delta}{2}\right\rceil+1\right)\left(\left\lfloor\frac{\Delta}{2}\right\rfloor+1\right)}n(G).$$

The two excluded graphs show that the corresponding bound from the preceding theorem is not true for graphs of maximum degree $3$ or $4$ without exceptions. The conjecture asserts that these are the only exceptions.