  We study the problem of finding a minimum $k$-critical-bipartite graph of
order $(n,m)$: a bipartite graph $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$ yields
$G'$ that has a complete matching, i.e., a matching of size $m$. Cichacz and
Suchan solved the problem for biregular bipartite graphs. Here, we extend their
results to bipartite graphs that are not biregular. We also prove tight lower
bounds on the connectivity of $k$-critical-bipartite graphs.
