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

Ameneh Farhadian

Published 2018-05-14Version 1

The paper shows that almost every $n$-vertex graph is, uniquely, determined by its subgraphs with $3 \log_2{n}$ vertices. Therefore, for checking the isomorphism of almost every pair of $n$-vertex graphs, it is sufficient to compare their $3 \log_2{n}$-vertex subgraphs.