I'm having trouble solving this exercise I found about isomorphic graphs.
It reads
Among the following graphs, which pairs are isomorphic? For each pair that are isomorphic, describe an isomorphism (bijection of vertices preserving adjacency) between them. For each pair that are not isomorphic, give a property preserved under isomorphism that one graph has but the other graph does not.
I've been referencing the vertices and counting the cycles but I don't know if that's all there is to it. I know that a, b and d have vertices that line up well, but c's don't. On the other hand a, b and c have cycles for 1 of 5 but d's is 4. Any help is appreciated.
Best Answer
The graph $G_2$ is the only one containing a cycle of length $3$, so it isn't isomorphic to any of the other graphs.
Among $G_1$, $G_3$ and $G_4$ only $G_4$ contains a cycle of length $4$.
The remaining two graphs $G_1$ and $G_3$ are in fact isomorphic. One possible isomorphism $G_1\to G_3$ is given by $$ 1\mapsto 1,\ 2\mapsto 2,\ 3\mapsto 3,\ 4\mapsto 8,\ 5\mapsto 9,\\ 6\mapsto 10,\ 7\mapsto 4,\ 8\mapsto 5,\ 9\mapsto 6,\ 10\mapsto 7. $$
I found this by considering $G_1$ as the two $5$-cycles $1,2,3,4,5$ and $6,7,8,9,10$ connected by $5$ edges. In the same way $G_3$ can be described as two $5$-cycles $1,2,3,8,9$ (top half) and $10,4,5,6,7$ (bottom half) connected by $5$ edges. Just check that the $5$ connecting edges are identified under the above map.