Let $G_1$, $G_2$ be the graphs shown below:
Decide if $G_1$ and $G_2$ are isomorphic. If so, exhibit an isomorphism. Otherwise exhibit an invariant property for isomorphism that one of the two graphs owns and the other doesn't.
My attempt
$G_1$ and $G_2 $have the same number of vertices and edges, and also the same degrees. So, the next step is to find a bijective function that checks the definition of isomorphism throug adjacency matrices. And that's where I have my problem: I can't understand the reasoning that leads to the construction of the two matrices, in practice.
Any hints?
Right. It's a little difficult to explain an answer since the graphs aren't labelled. But I'll give it a shot.
Right, so the an isomorphism is a bijection between the two vertex sets of $G_1$ and $G_2$. I'll explain the required isomorphism thus. Map the circled vertices to each other preserving colour codes. And map the remaining $4$-cycle (square) appropriately. This will give you an isomorphism.
How did I get here:
Well an isomorphism is a relation that preserves vertex adjacency in two graphs. Examining the definition properly you will understand that two graphs are isomorphic implies vertices in both graphs are adjacent to each other in the same pattern. So the geometric picture of a graph is useless. Only the information that states which vertex is adjacent to which others is important. So I can move a vertex $a$ freely in space as long as I do not disconnect the edges that connect $a$ to its neighbours. So in $G_2$ lift all $4$ circled vertices from the plane. Can you picture a cube? But $G_1$ is not exactly a cube. It is slightly distorted - the blue vertices are adjacent to irregular ones. In the cube that is $G_2$ now, draw a diagonal connecting the orange vertices and flip the blue vertices across this diagonal. If you can picture it, you will find the resulting shape is identical to the one in $G_1$. Both graphs can be represented by the same picture. They are isomorphic. Map the vertices that are in similar locations to each other and you have your bijective function.
Now, I don't know much about adjacency matrices but this is what I gathered. You should be able to permute the rows and columns of a matrix of one graph to obtain the other to say the two are isomorphic. But then you can see this is exactly what we do by moving vertices in geometric space. Vertices are represented by rows and columns and what we do is to flip it here and there to obtain one from the other. I hope this helps you understand the intuition behind isomorphism.
I'm sorry can't help you by writing down the matrices without labelling them which is too tedious a task (I'm not good with paint), but it shouldn't be too hard. Just identify the rows and columns of the circled vertices and flip them around.
Hope I helped..