0
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – D.W. Jan 5 '15 at 6:02
5
$\begingroup$

No. If two graphs have different degree sequences, they are definitely not isomorphic, so the algorithm "half-works". But consider a six cycle versus two three-cycles. Both graphs have six vertices, all of degree two; they are not isomorphic. Indeed, this counterexample shows that nothing based solely on degrees can work.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.