Let G be a simple (X,Y)-bipartite graph such that $|X| = |Y| = r$ and $|E(G)| > (k-1)r$. Let $M$ be a maximum matching for $G$. Show that $|M| \geq k$.
I know that a minimum cover $K$ on $G$ is such that $|K| \leq r$ (at most an entire partition of $G$). Moreover, for a bipartite graph we have that $\alpha(G) + |K| = |V(G)|$ and $|K| = |M|$. So,
$|M| = |K| = |V(G)| - \alpha(G) \leq r.$
Where to go from here?
On
Without using König's theorem, we can actually get a slightly stronger result, that is, every maximal matching in your graph has size at least $k$.
Let $M$ be a maximal matching of size $\ell \leq k-1$. We seek to augment this matching and thus derive a contradiction. Arrange the vertices of the bipartite graph as so: enumerate the $X$ side by $x_1, \dots, x_r$ and the $Y$ side by $y_1, \dots, y_r$, with $x_i y_i \in M$ for all $i \in \{1, \dots, \ell\}$. Clearly there are no edges between any $x_i$ and $y_j$ for $i, j \in \{\ell+1, \dots, r\}$, or else we could augment the matching. Additionally, for each $i \in \{1, \dots, \ell\}$ and $j \in \{\ell+1, \dots, r\}$, at most one of the edges $x_i y_j$ and $x_j y_i$ exists, since if they both existed we'd have an augmenting path for $M$. Then the number of edges in this graph is at most $$ \ell \cdot \ell + \ell \cdot (r - \ell) = \ell \cdot r \leq (k-1)\cdot r $$ contradicting the hypothesis that $|E| > (k-1)r$. Thus any maximal matching must be of size at least $k$.
Note that this line of thinking gives you the example that shows that this proposition is best possible.
By König's theorem, the size of the maximum matching $M$ equals the size of the minimum vertex cover $K$. For $\forall v\in K$, let $\mathsf{deg}(v)$ be the degree of $v$. Since $K$ is a vertex cover, we have $$ \sum_{v \in K} \mathsf{deg}(v) \geq |E| > (k - 1)\cdot r \tag{$\bigstar$} $$ Assume for contradiction that $|M| < k$; that is, $|K| \leq k - 1$. Then $$ \sum_{v \in K} \mathsf{deg}(v) \leq |K|\cdot r \leq (k - 1) \cdot r $$ contradicting with $(\bigstar)$.