 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. HenceThe 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.