[Math] Determining isomorphism of graphs

graph theory

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.enter image description here

Best Answer

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$.

Related Question