Solution 4.1.3.1.

The graphs are NOT equal, since $\{a,d\} \in E_1$ but $\{a,d\} \notin E_2\text{.}$ However, since both graphs contain the same number of vertices and same number of edges, they might be isomorphic (this is not enough in most cases, but it is a good start).

We can try to build an isomorphism. How about we say $f(a) = b\text{,}$ $f(b) = c\text{,}$ $f(c) = d$ and $f(d) = a\text{.}$ This is definitely a bijection, but to make sure that the function is an isomorphism, we must make sure it respects the edge relation. In $G_1\text{,}$ vertices $a$ and $b$ are connected by an edge. In $G_2\text{,}$ $f(a) = b$ and $f(b) = c$ are connected by an edge. So far, so good, but we must check the other three edges. The edge $\{a,c\}$ in $G_1$ corresponds to $\{f(a), f(c)\} = \{b,d\}\text{,}$ but here we have a problem. There is no edge between $b$ and $d$ in $G_2\text{.}$ Thus $f$ is NOT an isomorphism.

Not all hope is lost, however. Just because $f$ is not an isomorphism does not mean that there is no isomorphism at all. We can try again. At this point it might be helpful to draw the graphs to see how they should match up.

$The graph G1 with four vertices arranged in a diamond. The top vertex (a) is connected to the three other vertices (d on the left, b on the right, and c below). There is one additional edge between d and c.$

$The graph G2 with four vertices arranged in a diamond. The top vertex (a) is connected to the the vertices c below and b on the right. There is two additional edges between d (left) and c and between b and c .$

Alternatively, notice that in $G_1\text{,}$ the vertex $a$ is adjacent to every other vertex. In $G_2\text{,}$ there is also a vertex with this property: $c\text{.}$ So build the bijection $g:V_1 \to V_2$ by defining $g(a) = c$ to start with. Next, where should we send $b\text{?}$ In $G_1\text{,}$ the vertex $b$ is only adjacent to vertex $a\text{.}$ There is exactly one vertex like this in $G_2\text{,}$ namely $d\text{.}$ So let $g(b) = d\text{.}$ As for the last two, in this example, we have a free choice: let $g(c) = b$ and $g(d) = a$ (switching these would be fine as well).

We should check that this really is an isomorphism. It is definitely a bijection. We must make sure that the edges are respected. The four edges in $G_1$ are

\begin{equation*} \{a,b\}, \{a,c\}, \{a,d\}, \{c,d\}\text{.} \end{equation*}

Under the proposed isomorphism these become

\begin{equation*} \{g(a), g(b)\}, \{g(a), g(c)\}, \{g(a), g(d)\}, \{g(c), g(d)\} \end{equation*}

\begin{equation*} \{c,d\}, \{c,b\}, \{c,a\}, \{b,a\}\text{,} \end{equation*}

which are precisely the edges in $G_2\text{.}$ Thus $g$ is an isomorphism, so $G_1 \cong G_2$