Random Graph Isomorphism

A straightforward linear time canonical labeling algorithm is shown to apply to almost all graphs (i.e. all but o(2^( subarrayl n \\ 2 subarray ) )) of the 2^( subarrayl n \\ 2 subarray ) graphs on n vertices). Hence, for almost all graphs X, any graph Y can be easily tested for isomorphism to X by an extremely naive linear time algorithm. This result is based on the following: In almost all graphs on n vertices, the largest n0.15 degrees are distinct. In fact, they are pairwise at least n0.03 apart.