A problem of Erdős and Entringer [EnEr72], who constructed a graph with\[\gg 2^{\binom{n}{2}-O(n^{3/2+o(1)})}\]many unique subgraphs. This was improved by Harary and Schwenk [HaSc73] and then by Brouwer [Br75], who constructed a graph with\[\gg \frac{2^{\binom{n}{2}-O(n)}}{n!}\]many unique subgraphs.

Note that there are $\sim 2^{\binom{n}{2}}/n!$ many non-isomorphic graphs on $n$ vertices (folklore, often attributed to Pólya), and hence the bound in the problem statement is trivially best possible.

Erdős believed Brouwer's construction was essentially best possible, but Spencer suggested that $\gg \frac{2^{\binom{n}{2}}}{n!}$ may be possible. Erdős offered \$100 for such a construction and \$25 for a proof that no such construction is possible.

Bradač and Christoph [BrCh24] have proved the answer is no: if $f(n)$ is the maximum number of unique subgraphs in a graph on $n$ vertices then\[f(n) = o\left(\frac{2^{\binom{n}{2}}}{n!}\right).\](Quantitatively the $o(1)$ in their argument can be taken to be $O(\frac{\log\log\log n}{\log\log n})$.)

View the LaTeX source