grid (2,0); (0,-1) rectangle (6,3); (0.5,3.5) node [$1$]{}; (1.5,3.5) node [$2$]{}; (2.5,3.5) node [$3$]{}; (3.5,3.5) node [$4$]{}; (4.5,3.5) node [$5$]{}; (5.5,3.5) node [$6$]{}; (-0.5,2.5) node [$1$]{}; (-0.5,1.5) node [$2$]{}; (-0.5,0.5) node [$3$]{}; (-0.5,-0.5) node [$4$]{};

(0,2) grid (6,3); (0,1) grid (5,2); (0,0) grid (3,1); (0,-1) grid (2,0); (.5,.5) circle (5pt); (2.5,2.5) circle (5pt); (4.5,1.5) circle (5pt); (0,-1) rectangle (6,3); (0.5,3.5) node [$1$]{}; (1.5,3.5) node [$2$]{}; (2.5,3.5) node [$3$]{}; (3.5,3.5) node [$4$]{}; (4.5,3.5) node [$5$]{}; (5.5,3.5) node [$6$]{}; (-0.5,2.5) node [$1$]{}; (-0.5,1.5) node [$2$]{}; (-0.5,0.5) node [$3$]{}; (-0.5,-0.5) node [$4$]{};

Bipartite Minimizer
===================

In this section we prove Theorem \[bipartite\]. We are motivated to look at the bipartite case by the following lemma.

\[minimize\] Given a threshold graph $G$ with vertex set $V$, let $V = K \cup (V\setminus K)$ be a partition of the vertex set such that $G[K]$ forms a clique and $G[V\setminus K]$ forms an independent set. Suppose $\abs{K} = s$. Let $B$ be the bipartite graph with partite sets $K$ and $V\setminus K$ and edge set $E(K, V\setminus K)$. Then $$m(G) = \sum_{k\geq 0} m_k(B) \cdot m(K_{s-k}).$$

Fixing a matching $M$ in $B$ of size $k$, there are exactly $m(K_{s-k})$ matchings in $G$ that contain $M$. So 