Unique subgraphs are rare

A folklore result attributed to Pólya states that there are $(1+o(1))2^{\left(\genfrac{}{}{0px}{}{n}{2}\right)}\mathrm{/}n!$ non-isomorphic graphs on $n$ vertices. Given two graphs $G$ and $H$, we say that $G$ is a unique subgraph of $H$ if $H$ contains exactly one subgraph isomorphic to $G$. For an $n$-vertex graph $H$, let $f(H)$ be the number of non-isomorphic unique subgraphs of $H$ divided by $2^{\left(\genfrac{}{}{0px}{}{n}{2}\right)}\mathrm{/}n!$ and let $f(n)$ denote the maximum of $f(H)$ over all graphs $H$ on $n$ vertices. In 1975, Erdős asked whether there exists $\delta >0$ such that $f(n)>\delta$ for all $n$ and offered $\mathrm{\$}100$ for a proof and $\mathrm{\$}25$ for a disproof, indicating he does not believe this to be true. We verify Erdős’ intuition by showing that $f(n)\to 0$ as $n$ tends to infinity, i.e. no graph on $n$ vertices contains a constant proportion of all graphs on $n$ vertices as unique subgraphs.