# Graph isomorphism and finding bijection

Let us consider two bangles. On these bangles let us add $$8$$ pearls on each bangle, the sequence of colors of pearls are same on both bangle. But the sequence of labels on pearls is not same. Now assuming the pearls as vertices of graph and circumference of bangle as edges of a graph, these bangles would correspond to two undirected graph, say $$G_1$$ and $$G_2$$ .

1. As far as I think these two graphs would be isomorphic as their number of vertices, edges and connectedness and other properties are same. Additionally, I cannot think of a property that is not same in both. Am I right?

2. Graph isomorphism means that there exist a bijection $$f$$ such that $$f:V(G_1) \to V(G_2)$$. So, this bijection must be a function. The question is does such a function means that we can define a formula to get vertex of $$G_2$$ as output when the input is a vertex of $$G_1$$. (Obviously it should preserve the edges)

3. Is finding such an $$f$$ equals to graph isomorphism problem.

• Your two graphs are both cycles on eight vertices. The graph isomorphism problem concerns general graphs, not just cycles. Commented Mar 10 at 11:59
• @GerryMyerson I know that they are cycle but my questions are still not answered. If you can please answer it. Commented Mar 31 at 11:00
• Yes, the two graphs are isomorphic. No, it's not because you can't think of a property they don't share. Graph isomorphism means a lot more than a bijection on vertices. Not every function can be expressed as a formula (although you haven't made it clear what you mean by the word, formula). The graph isomorphism problem asks you to determine whether there is a bijection on vertices that induces a bijection on edges. All of this information is readily available in intro graph theory textbooks, as well as dozens of websites. Commented Mar 31 at 12:26
• @GerryMyerson By formula I meant an operation whose input is a value of $G_1$ and output value of $G_2$ Commented Apr 1 at 3:35