How can we determine if any pair of the following graphs are isomorphic to each other? Is there an efficient way to know for sure? The obvious things to check for (number of edges, vertices, degrees) aren't fruitful because all three graphs have the same of each. Any suggestion appreciated.
- Anybody can ask a question
- Anybody can answer
- The best answers are voted up and rise to the top
Two graphs are isomorphic if and only if their complements are isomorphic. The complement of $G_1$ is a $7$-cycle, while the complements of $G_2$ and $G_3$ are both the disjoint union of a $4$-cycle and a $3$-cycle. Thus $G_2$ and $G_3$ are isomorphic to each other but not to $G_1$.
As for the general question: No efficient general procedure is known for determining whether two graphs are isomorphic.
The graph isomorphism problem is somewhat famous for being one of the few problems in NP that are suspected not to have a polynomial-time algorithm, yet haven't been proved NP-complete.
Just to share one observation using graph coloring:
So you can actually show that $G_1\not\cong G_2$ and $G_1\not\cong G_3$.
A 3-coloring of $G_2$ (left-to-right, then down):
A 3-coloring of $G_3$ (same orientation):
And one may prove that $\chi(G_1)> 3$ by starting with the coloring:
But the converse is not true.
However, you can discover the "right way" to label the graphs guided by the coloring.
Certainly not an efficient method for this problem.
You can check if two graphs are not isomorphic by looking at the spectrum of the adjacence matrix...