Almost every $n$-vertex graph is determined by its $3{\log }_{2}n$-vertex subgraphs

Abstract

The paper shows that almost every $n$-vertex graph is such that the multiset of its induced subgraphs on $3{\log }_{2}n$ vertices is sufficient to determine it up to isomorphism. Therefore, for checking the isomorphism of a pair of $n$-vertex graphs, almost surely the multiset of their $3{\log }_{2}n$-vertex subgraphs is sufficient .