= Solution
Take a maximal <matching in a graph> with $m$ edges and let $S$ be its $2m$ endpoints. Maximality makes its complement an <independent set>, since an edge wholly outside $S$ could be added. Every vertex outside $S$ therefore sends all its $k$ edges into $S$, giving $k(n-2m)$ crossing edges. Every vertex in $S$ already uses at least one incident edge inside $S$, its matched edge, so it sends at most $k-1$ outside. Hence
$$
k(n-2m)\leq2m(k-1),\qquad
\boxed{m\geq\frac{kn}{4k-2}.}
$$
The maximum <matching in a graph> is at least this large. For $k=2$, take any disjoint union of $r$ triangles. It is 2-regular, has $n=3r$ vertices and matching number $r=n/3$, since each triangle contributes exactly one edge. As $r$ varies this gives infinitely many equality examples.
Back to article page
