\leq r$ and $B\in {\mathcal{B}}_{\ell,r,e}$. Then $$m(B)\geq m(L_{\ell,r}(e))$$ and $$m_k(B)\geq m_k(L_{\ell,r}(e)).$$

To prove Theorem \[general\], we will first show that the graph attaining the minimum number of matchings is threshold. In Section \[Threshold\] we discuss the results we need concerning threshold graphs. In Section 3 we prove Theorem \[bipartite\], i.e., that there is a bipartite graph that simultaneously minimizes the number of matchings of each size. Finally, we use the bipartite case to show that the lex or colex graph minimizes $m(G)$ and $m_k(G)$ in the family ${\mathcal{G}}_{n,e}$ in Section 4.

Threshold Graphs {#Threshold}
================

Threshold graphs appear as an answer to many extremal questions, especially those in which it is advantageous to have all the edges “bunched together”. For instance in the class ${\mathcal{G}}_{n,e}$ threshold graphs maximize the number of independent sets and minimize homomorphisms into the Widom-Rowlinson graph [@WidomRowlinson].

There are many equivalent definitions of threshold graphs. The one that gives them their name is as follows.

A simple graph $G$ is a *threshold graph* if there exists a function $w: V(G) \to {\mathbb{R}}$ and a threshold $t\in {\mathbb{R}}$ such that $xy\in E(G)$ if and only if $w(x)+w(y)\geq t$.

The following lemma describes an alternative characterization that we 