Graphs with n vertices and m edges

61 Views Asked by At

Which graphs on $n$ vertices and $m$ edges have the maximal number of independent sets? I was thinking that if $m = \sum_{i=0}^{r} \binom{a_{i}}{2}$, with the $a_{i}$'s maximal and non-increasing, then the graphs with cliques of size $a_{i}$ would be good, but I am not sure how to proceed.