move later to show that we can find a graph that minimizes $m_k(G)$ in ${\mathcal{G}}_{n,e}$ that is threshold.

Let $G$ be a graph and $x$ and $y$ two vertices in $G$. Define $$N_G(x,{\overline}{y}) =\{v\in V(G)\setminus \{x,y\}: v\sim x,v\not\sim y\}.$$ Let $G_{x\to y}$ be the graph formed by deleting all edges between $x$ and $N_G(x,{\overline}{y})$ and adding all edges from $y$ to $N_G(x,{\overline}{y})$. This is called the *compression of $G$ from $x$ to $y$*. It is clear that $G_{x\to y}$ has the same number of edges as $G$.

We will begin our proof of Theorem \[general\] by repeatedly compressing a graph that minimizes the number of matchings. The following lemma will allow us to be sure that we are making progress, and not compressing round and round in a circle. The variance of the degree sequence, or (essentially equivalently) the quantity $$d_2(G) = \sum_{v\in V(G)} d(v)^2$$ strictly increases whenever we do a non-trivial compression.

\[lem:allcompressed\] Given $x,y\in V(G)$, $e(G_{x\to y}) = e(G)$ and $d_2(G_{x\to y})\geq d_2(G)$. If $N[x]\not\subseteq N[y]$ and $N[y] \not\subseteq N[x]$ then $d_2(G_{x\to y}) > d_2(G)$. $\hfill$ $\blacksquare$

\[cor:allcompressed2\] Suppose that ${\mathcal{G}}$ is a family of graphs on a fixed vertex set $V$ such that for any $G'\in{\mathcal{G}}$ and 