Number of nonisomorphic subgraphs in an $n$-point graph

A. D. Korshunov

Matematičeskie zametki, Tome 9 (1971) no. 3, pp. 263-273

Résumé

Let $\mathfrak{G}(n)$ be the set of all nonoriented graphs with $n$ enumerated points without loops or multiple lines, and let $\nu_k(G)$ be the number of mutually nonisomorphic $k$-point subgraphs of $G\in\mathfrak{G}(n)$. It is proved that at least $|\mathfrak{G}(n)|(1-1/n)$ graphs $G\in\mathfrak{G}(n)$ possess the following properties: a) for any $k\in[6\log_2n, cn+5\log_2n]$, where $c=-c\log_2c-(1-c)\times\log_2(1-c)$ and $c>1/2$, we have $\nu_k(G)>C_n^k(1-1/n^2)$; b) for any $k\in[cn+5\log_2n, n]$ we have $\nu_k(G)=C_n^k$. Hence “almost all” graphs $G\in\mathfrak{G}(n)$ contain $\nu(G)\sim2^n$ pairwise nonisomorphic subgraphs.