Graph isomorphism question

Question

I'm trying to show that the following two graphs are isomorphic.

I've tried defining a few bijections between $V(G)$ and $V(H)$, one of which as follows:

$$\phi: a \mapsto a, b \mapsto b, c \mapsto c, d \mapsto g, e \mapsto h, f \mapsto f, g \mapsto e, h \mapsto d$$

Using this bijection most edges in $G$ mapped to edges in $H$ except for $3$ edges, namely:

$$cg \in E(G) \mapsto ce \notin E(H)$$ $$dh \in E(G) \mapsto gd \notin E(H)$$ $$ef \in E(G) \mapsto hf \notin E(H)$$

I would really appreciate if someone could find a bijection that works because I've been scratching my head for hours and it's doing my head in.

Answer 1

We may as well let $a \mapsto a$, because the graph $G$ is symmetric on any rotation, so if there is an isomorphism $G \to H$ then there is an isomorphism in which $a \mapsto a$.

Let's guess $b \mapsto b$. Then we need to find a rectangle in $H$ which corresponds to the $G$-rectangle $abfe$.

That rectangle has to be $abcd$, by trial and error.

So we must have $f \mapsto c, e \mapsto d$.

Now, the only other $G$-vertex $b$ is connected to is $c$, and the only other $H$-vertex $b$ is connected to is $f$, so $c \mapsto f$.

Can you continue? Find the image of the $G$-rectangle $bcgf$, for example.

Answer 2

Hint: Your isomorphism $\phi$ took a line graph $abcdefgh$ to a nonlinear graph $abcghfed$.

Answer 3

I looked at the $5$-cycle in $H$, $abfed$. The $5$-cycles in $G$ all involve tracing the outside circle, so we should be able to arbitrarily map this to $abcde$ in $G$. Then the vertices not involved in the cycle, $\{c,g,h\}$, connect to $\{bdg, cfh, aeg\}$ in $H$ respectively which means their image vertices in $G$ connect to $\{be?, ?c?, ad?\}$ and thus the vertices map to $\{f,g,h\}$. This gives the full mapping as $(a,b,c,d,e,f,g,h)_G\mapsto (a,b,f,e,d,c,g,h)_H$

Once worked out, this can be seen as twisting the right-hand half of H through $180°$ on the horizontal axis.