# To detect isomorphic graphs Is it enough to check if they have the same number of same degree vertices?

Given two lists of non directional graph edges e.g. [(1,3),(3,5),(5,1),(5,7)] [(4,5),(2,3),(3,4),(4,2)] In order to check if the two graphs are isomorphic is it enough to count the vertices with the same degree between them?

e.g. Vertice   1: 2    1: 0
2: 0    2: 2
3: 2    3: 2
4,6: 0    4: 3
5: 3    5: 1
7: 1    6,7: 0


So in our example: both graphs have 2 vertices with 2 edges 1 with 3, one with one and 3 with 0

• What have you tried? We expect you to make a significant effort before asking, and to show us in the question what you tried. Have you tried constructing a counterexample? If not, spend some time playing around with graphs to try to see if you can construct a counterexample. You might also read Wikipedia's article en.wikipedia.org/wiki/Graph_isomorphism and ponder the fact that if the answer to your question was yes, then we'd have a polynomial-time algorithm for graph isomorphism. – D.W. Jan 5 '15 at 6:02