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?
