(3pt) ; (3) circle (3pt) ; (4) circle (3pt) ; (5) circle (3pt) ; (6) circle (3pt) ;

=\[bend left\]

(0)(1)

(0)(2)

(1)(2)

(0)(3) (1)(3) (2)(3)

(0)(4)

(1)(4)

Our main result is that $m(G)$ and $m_k(G)$ are each minimized by either the lex graph or the colex graph.

\[general\] For all graphs $G$ with $n$ vertices and $e$ edges, and for all $k$, $$m(G) \geq \min\{ m({\mathcal{L}}(n,e)), m({\mathcal{C}}(n,e)\}$$ and $$m_k(G) \geq \min\{ m_k({\mathcal{L}}(n,e)), m_k({\mathcal{C}}(n,e)\}.$$

Suppose $n = \ell+ r$ with $\ell\leq r$ and $e\leq \ell r$. Write $e = qr+c$ where $0\leq c < r$. The *lex bipartite graph* with $e$ edges and partite sets $L$ and $R$ of size $\ell$ and $r$ respectively is the bipartite graph in which $q$ vertices in $L$ have degree $r$ and one vertex in $L$ has degree $c$. We will denote this graph by $L_{\ell,r}(e)$. Note that the lex bipartite graph contains the first $e$ edges of $E(L,R)$ in lex order.

A core part of the proof of Theorem \[general\] is to establish that, for all $k\geq 0$, $L_{\ell,r}(e)$ minimizes $m_k(G)$ in the class ${\mathcal{B}}_{\ell,r,e}$. It is key that there is a unique minimizer in the bipartite case.

\[bipartite\] Suppose $1\leq k\le \ell 