then extended to the general case by Zhao [@Zhao].

\[thm:KahnZhao\] If $G$ is a $d$-regular graph then $\operatorname{ind}(G)$, the number of independent sets in $G$, satisfies $$\operatorname{ind}(G) \le \left(2^{d+1}-1\right)^{\frac{n}{2d}} = (\operatorname{ind}(K_{d,d}))^{\frac{n}{2d}}.$$

Such problems have been studied (extensively) for the number of perfect matchings in a graph: see for instance [@Alon; @KahnCuckler; @EntropyKahnLovasz; @Gross] and others. Usually these results concern regular graphs or graphs with a given degree sequence. In another vein there has been work on determining which graph with given numbers of vertices and edges maximizes or minimizes a given counting parameter. (We write ${\mathcal{G}}_{n,e}$ for the class of graphs having $n$ vertices and $e$ edges.) For instance Cutler and Radcliffe [@WidomRowlinson; @TheFox] determined which graphs have the largest number of homomorphisms in various fixed images graphs $H$. They also showed that the Kruskal-Katona Theorem implies that the lex graph has the greatest number of independent sets among graphs in ${\mathcal{G}}_{n,e}$. A classic paper of Ahlswede and Katona [@Ahlswede] determines the minimum number of pairs in non-incident edges a graph in ${\mathcal{G}}_{n,e}$ can have. (Which is of course the same as maximizing the number of pairs of incident edges.)

In this paper we solve the problem of determining which 