For sure your solution is around the graph isomorphism. Indeed you want to see whether two graphs (ERDs in fact) are isomorphic or not. First of all please keep in mind that you are facing a really hard problem:
"it is one of a very small number of problems belonging to NP neither known to be solvable in polynomial time nor NP-complete: it is one of only 12 such problems listed by Garey & Johnson (1979), and one of only two of that list whose complexity remains unresolved."(1)
As you are working on a project so run time is of big concern for you so I recommend you to implement an approximate algorithm and specially read this paper:
Approximate Graph Isomorphism by V. Arvind et al.
http://eccc.hpi-web.de/report/2012/078/download [+ please consider the copy right if exists.]