Are two Graph isomorphic?

Question

I think I have a method to solve the problem. I am aware that its NP complete and its so tempting to solve. I am aware that I can be wrong 99.99% but I wanted to give a shot at it. I want to put it to test.

Given 2 Graphs : A, B (No Self loops / No Multi-edges)

The Idea is to create a unique signature for each vertex or node based on the edges.

1) sort the nodes based on the degree of each node. 2) take the node with the highest degree. here we have [A, D, E, F] with degree of 3. Lets take A and it has a degree of 3 so let us start building a signature. we represent it as "C" and now we take the adj nodes with max degree which is D and it has a degree of 3. Now the signature is "CC". next we take next highest degree node that is either B or C each has a degree of 2. so now the signature is "CCBB".

3) repeat the above sets for the next node that is D and we get a signature of "CCCC".

4) next for E - "CCCB". 5) next for G - "CCCB". 6) next for B - "BCC" 7) next for C - "BCB" 8) next for F - "BCB"

Do the same for the 2nd Graph we get:

• node 1 : "CCCB"
• node 5 : "CCCB"
• node 6 : "CCCC"
• node 7 : "CCBB"
• node 2 : "BCB"
• node 3 : "BCB"
• node 4 : "BCC"

so this proves that both the graphs are same. node(1, 5) = node (E, G). node(A) = node(7). node(D) = node(6). node(B) = node(4). node(C, F) = node (2,3).

Answer 1

Two three-regular graphs on six vertices are shown below. One is planar, the other is not, which implies they are non-isomorphic. As far as I understand, your procedure would produce the same signature for these graphs.

Answer 2

Actually, the graph isomorphism problem is not np hard. In fact there is a kinda recent paper describing a quasipolynomial algorithm (https://arxiv.org/abs/1512.03547). Their method starts at similar ideas to yours (looking at degree of nodes), but there are some cases that need more care. But you are right, most graphs you can think of can be solved by your method.

Note that the subgraph-isomorphism problem is np hard. I. E. Determining if one graph is isomorphic to a subgraph of another.