# Algorithm to check if an equivalent node exists on a different graph with different labelings

Let's say I have an undirected graph defined by a set of edges:

$$\{(1, 2), (0, 2, 3), (0, 1, 3), (1, 2)\}$$

This could be drawn as follows: Now, assume that I drew the same graph, but changed the numbers:

$$\{(1, 2, 3), (0, 3), (0, 3), (0, 1)\}$$

to form this: It's clear that these two graphs are identical, at least visually. This question goes into more detail about this problem, but I'm looking for a solution to a more specific focus.

Now, we'll focus in on the node that is called $$3$$ in graph 1, and $$1$$ in graph 2.

This node is represented as $$(1, 2)$$ in the first graph, and $$(0, 1)$$ in the second. Now, here's my problem:

Suppose I am given a list of edges $$b$$, and one specific node $$b_n$$ from that list of edges. Also suppose I am given another list of edges $$z$$, which may or may not be equivalent in size. I now need to find out whether $$z$$ contains some node $$z_n$$ which, ignoring labelling, is equivalent to $$b_n$$.

By equivalent, I mean that if we only focus on the node $$b_n$$, its direct neighbours, and the edges connecting to the neighbours, it would be identical to that of $$z_n$$ in the context of the given graph, ignoring the numbering/labelling.

E.g:

Given $$b=\{(1, 2), (0, 2, 3), (0, 1, 3), (1, 2)\}$$, $$n=3$$ (0-indexed), and $$z=\{(1, 2, 3), (0, 3), (0, 3), (0, 1)\}$$. We can find that the result is true in this case, since there exists $$n=1\Rightarrow z_n$$ such that, removing all labels, $$z_n$$ is essentially equal to $$b_n$$.

In a more complex example, take this graph: and this one: Here, $$b=\{(1, 2, 3), (3, 4), (0, 3), (0, 1, 2), (1)\}$$, $$n=4$$ and $$z=\{(4), (2, 3, 4), (1, 3), (1, 2), (1, 0)\}$$

We'd once again return true. $$b=\{(1, 2, 3), (0), (0, 3), (0, 2, 4, 5), (3, 5), (3, 4, 6), (5)\}$$, $$n=3$$ $$z=\{(1, 2, 3), (0, 7, 8), (0, 3), (0, 2, 4, 5), (3, 5), (3, 4, 6), (5, 9), (1, 8, 9), (1, 7, 9), (6, 7, 8)\}$$

Once again, this is true, because if we only do a shallow check then the node's direct neighbours are the same nodes despite the different numbering, even if the secondary neighbours are different.

My question is: Is there a generalised algorithm to check this, given the two graphs and an integer $$n$$? If so, what is the most computationally efficient method?

• It sounds like you consider two vertices equivalent if their neighbourhoods are isomorphic. So you still have to solve a graph isomorphism problem, but if the degree of the vertex is small then it might not be too expensive.
– user856
Oct 3, 2019 at 6:48
• @Rahul thanks! I know virtually nothing about the subject, so I'm sorry if the question seems quite obvious/easy. I'll look into what you said! Oct 3, 2019 at 6:56