  Galvin showed that for all fixed $\delta$ and sufficiently large $n$, the
$n$-vertex graph with minimum degree $\delta$ that admits the most independent
sets is the complete bipartite graph $K_{\delta,n-\delta}$. He conjectured that
except perhaps for some small values of $t$, the same graph yields the maximum
count of independent sets of size $t$ for each possible $t$. Evidence for this
conjecture was recently provided by Alexander, Cutler, and Mink, who showed
that for all triples $(n,\delta, t)$ with $t\geq 3$, no $n$-vertex {\em
bipartite} graph with minimum degree $\delta$ admits more independent sets of
size $t$ than $K_{\delta,n-\delta}$.
  Here we make further progress. We show that for all triples $(n,\delta,t)$
with $\delta \leq 3$ and $t\geq 3$, no $n$-vertex graph with minimum degree
$\delta$ admits more independent sets of size $t$ than $K_{\delta,n-\delta}$,
and we obtain the same conclusion for $\delta > 3$ and $t \geq 2\delta +1$. Our
proofs lead us naturally to the study of an interesting family of critical
graphs, namely those of minimum degree $\delta$ whose minimum degree drops on
deletion of an edge or a vertex.

Combinatorics