OPEN - $100

We say $H$ is a unique subgraph of $G$ if there is exactly one way to find $H$ as a subgraph (not necessarily induced) of $G$. Is there a graph on $n$ vertices with
\[\gg \frac{2^{\binom{n}{2}}}{n!}\]
many distinct unique subgraphs?

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 a construction and \$25 for a proof that no such construction is possible.