Isomorphism of two graphs using adjacency matrix

Question

How can I show that the following two graphs are isomorphic:

Steps:
The given graphs can be written as:

Answer 1

The adjacency matrix $A(G_2)$ is not symmetrical and one of the diagonal entry is non-zero. Most likely you have computed it wrongly.

To show isomorphism, it suffices to find permutation matrix $P$ such that $$PA(G_1)P^T=A(G_2).$$

The following observation might help you in constructing the matrix $P$.

$v_1$ corresponds to $w_5$.

$v_2$ corresponds to $w_6$.

$v_3$ corresponds to $w_2$.

$v_4$ corresponds to $w_3$.

$v_5$ corresponds to $w_4$.

$v_6$ corresponds to $w_1$.

Answer 2

In this case it is easier to find the isomorphism by looking at the graphs rather than their adjacency matrices. Observe that in the first graph, there are three paths from $v_5$ to $v_3$, two of which have length 2 and one of which has length 3. Similarly in the second graph from vertex $w_4$ to vertex $w_2$. The paths of length 3 must be mapped to each other. So, a bijection $f$ from the vertex set $\{v_1,\ldots,v_6\}$ of the first graph to the vertex set $\{w_1,\ldots,w_6\}$ of the second graph which preserves adjacency can be obtained.

Once you have the bijection $f$, observe that it corresponds to a permutation $\pi \in S_6$, where $\pi$ maps $i$ to $j$ if $f$ maps $v_i$ to $w_j$. Now, $\pi$ can be represented by a permutation matrix, and the adjacency matrix $A$ of the first graph and $B$ of the second graph satisfy the equation $PAP^T = B$.