  We study the problem of Minimum $k$-Critical Bipartite Graph of order $(n,m)$
- M$k$CBG-$(n,m)$: to find a bipartite $G=(U,V;E)$, with $|U|=n$, $|V|=m$, and
$n>m>1$, which is $k$-critical bipartite, and the tuple $(|E|, \Delta_U,
\Delta_V)$, where $\Delta_U$ and $\Delta_V$ denote the maximum degree in $U$
and $V$, respectively, is lexicographically minimum over all such graphs. $G$
is $k$-critical bipartite if deleting at most $k=n-m$ vertices from $U$ creates
$G'$ that has a complete matching, i.e., a matching of size $m$. We show that,
if $m(n-m+1)/n$ is an integer, then a solution of the M$k$CBG-$(n,m)$ problem
can be found among $(a,b)$-regular bipartite graphs of order $(n,m)$, with
$a=m(n-m+1)/n$, and $b=n-m+1$. If $a=m-1$, then all $(a,b)$-regular bipartite
graphs of order $(n,m)$ are $k$-critical bipartite. For $a<m-1$, it is not the
case. We characterize the values of $n$, $m$, $a$, and $b$ that admit an
$(a,b)$-regular bipartite graph of order $(n,m)$, with $b=n-m+1$, and give a
simple construction that creates such a $k$-critical bipartite graph whenever
possible. Our techniques are based on Hall's marriage theorem, elementary
number theory, linear Diophantine equations, properties of integer functions
and congruences, and equations involving them.
