How can I label vertices of the graph, so they are the same as on the other labeled graph?

Is there some algorithm to label equivalent vertices of unlabeled graph?

For example, suppose I have two distinct graphs $G_1$ and $G_2$, and they are isomorophic. However, $G_1$ has labeled vertices and endges, whereas $G_2$ has only edges labeled (edge labels might be different in $G_1$ and $G_2$). Is there any way how I can name vertices in $G_2$, so equivalent vertices to $G_1$ have the same labels?

So if $G_1$ and $G_2$ look something like this. I need $G_2$ to be like there.

1 Answer

This problem can be solved with canonical labelings: compute the canonical labeling of both $G_1$ and $G_2$; if this results in the same (labeled) graph, then $G_1$ and $G_2$ are isomorphic. Then vertices with the same label (in the canonical labeling) are equivalent. But please note that both isomorphisms and canonical labelings are only unique up to automorphism. (e.g.: in your example, vertex 1 and 3 cannot be distinguished.)

The theoretical complexity of the graph isomorphism-problem is still unknown, but in practice there are fast programs such as nauty which will do the job even for large graphs.