On the isomorphism of graphs having some eigenvalues of moderate multiplicity

Graph Isomorphism is one of the most prominent problems in computer science, which is not known to be NP-complete or polynomial time solvable. Babai, Grigoryev, and Mount (STOC 1982) showed that for graphs, which only have eigenvalues of bounded multiplicity (except at most one eigenvalue), this problem is in P. Evdokimov and Ponomarenko (Combinatorica 1999) extended the result of Babai et al. to graphs for which all eigenvalues have multiplicity O(log⁡n/log⁡log⁡n)O(log⁡n/log⁡log⁡n), where n is the number of vertices. In this paper we present an elementary   proof that if for two graphs the sum of squares of the multiplicities corresponding to the eigenvalues with unbounded multiplicity is O(log⁡n/log⁡log⁡n)O(log⁡n/log⁡log⁡n), then isomorphism testing can be solved in polynomial time. Although our result is completely covered by Evdokimov and Ponomarenko, and hence it is not new, our proof only uses elementary methods and is completely different from their considerably more demanding approach.