there are $m_k(B) \cdot m(K_{s-k})$ matchings in $G$ that contain a $k$-matching in $B$. Summing over all possible sizes of matchings in $B$ we count every matching in $G$ exactly once.

Theorem \[bipartite\] states that for a given $k$ there is a graph that simultaneously minimizes every $m_k(G)$ in ${\mathcal{B}}_{\ell,r,e}$. We will first show that there is a threshold bipartite graph that minimizes $m_k(G)$ in ${\mathcal{B}}_{\ell,r,e}$. We will then use moves on the associated Young diagrams to show that the lex bipartite graph $L_{\ell,r}(e)$ minimizes $m_k(G)$ for all $k$.

\[differencegraph\] Suppose $G$ is a bipartite graph with bipartition $(X,Y)$. Let $u,v \in X$. Then for every $k\geq 0$ the graph $H:= G_{u \to v}$ has at most as many $k$-matchings as $G$.

We will construct an injection from ${\mathcal{M}}(H)\setminus {\mathcal{M}}(G)$ to ${\mathcal{M}}(G)\setminus {\mathcal{M}}(H)$ that preserves size. It then follows that $m_k(H)\leq m_k(G)$ for all $k$. We define a replacement function $r: E(H) \to E(G)$ by $$r(e) = \begin{cases}
uy &\text{ if } e=vy \text{ for } y \in N_G(u,{\overline}{v})\\
vz &\text{ if } e=uz\\
e  &\text{otherwise}
\end{cases}.$$

Given $e$ in the edge set of $H$, we claim that $r(e)$ is an edge in $G$. If $y\in N_G(u,{\overline}{v})$, then $uy\in E(G)$. 