Prove two graphs are isomorphic

Solution 1:

Unfortunately, two non-isomorphic graphs can have the same degree sequence. See here for an example. Checking the degree sequence can only disprove that two graphs are isomorphic, but it can't prove that they are. In this case, I would just specify my isomorphism (which you've basically done, by identifying the vertices A and T, B and U, and so on) and then show that two vertices are connected by an edge in the original graph if and only if they are connected in the image. It's a little tedious, but should be something you can apply in general to these kinds of problems.

Solution 2:

To show that the two graphs are isomorphic, apply the given definition. Let's call the graph on the left $G[V_1,E_1]$, and the graph on the right $G[V_2,E_2]$. Now give an explicit bijection $$f:\ V_1\ \longrightarrow\ V_2,$$ and show that if $\{e_1,e_2\}\in E_1$, then $\{f(e_1),f(e_2)\}\in E_2$.

Checking that $\operatorname{Deg}(e)=\operatorname{Deg}(f(e))$ for all $e\in V$ is not sufficient: Given an isomorphism $f$, we obtain another bijection $g:\ V_1\ \longrightarrow\ V_2$ by switching $U$ and $W$, that is; $$g(e)=\left\{\begin{array}{cc}W&\text{ if }f(e)=U\\U&\text{ if }f(e)=W\\f(e)&\text{ otherwise}\end{array}\right.$$ The degrees are preserved, but this is not an isomorphism.

Solution 3:

First Make Adjacency matrix for both graphs.

These matrices would be square and symmetrical. (If No multiple or directed edges)

The main diagonal would be all zeroes (if no loops)

if number of 1s and 0s are not the same in both matrices then its not isomorphic surely. If they are same then it may be isomorphic.

Take any one of the matrices.

Now you can swap 2 coloumns of this matrix but when you do that you must also swap the same rows.

So while swapping row2 and row3, you should immediately swap col2 and col3 as well. Order of swapping doesnt matter. Since its square matrix, all columns will have corresponding rows.

Doing this would simply swap the vertex's position in adjacency matrix and so changing the mapping of each vertex.

By use of our pattern finding ability we can choose which rows and columns to swap so that one matrix would look exactly like the other. You would get it in max 3-4 swaps.

Its quite easy since they are square symmetrical.

If they are not isomorphic then you might try to swap rows and cols endlessly trying to match the pattern but by little intuition you can avoid that.

They are isomorphic if adjacency matrix look same. This matrix would give you the mappings.

So its like trying to find a mapping from all possible mappings of one graph, that look exactly like the other adjacency matrix by cleaverly swapping position of vertices (by swaping rows and cols). Does not work so good for huge graphs.

Solution 4:

I find discrepancy in the first statement of your's - there are 7 vertices in both the graphs then you have 6 edges in both the graphs. This basic condition if true then it can further be proved that the two given simple graphs can be isomorphic or not? - depending onto the result.

Next you made mappings from G(1st graph) to H(2nd graph)- which is correct but then also - you cannot say that these are isomorphic. What you need to do is - you need to make an adjacent matrix adj(G) and another adjacent matrix adj(h) where adj(h) will be as per the mappings you've done for the graph H using G!

if adj(G) and adj(h) are same, then you say that these graphs are isomorphic otherwise they aren't!

Hope you get it!