Unique subgraphs are rare

Abstract

A folklore result attributed to Pólya states that there are $(1+o(1))2^{\left(\genfrac{}{}{0ex}{}{n}{2}\right)}/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{}{}{0ex}{}{n}{2}\right)}/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 $\hat{I}´>0$ such that $f(n)>\hat{I}´$ for all $n$ and offered $\$100$ for a proof and $\$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.