0
$\begingroup$

If two graphs $G_i$ and $G_j$ are isomorphic, please provide a bijection from the vertex set of $G_i$ to $G_j$, if the two graphs are not isomorphic, please provide a structural difference graphs

enter image description here

As There is an answer how to find weather two graphs are isomorphism or not in this link

I was wondering in such cases like example above which none of the ways to to prove isomorphism work, Then how we can see which of them are isomorphism ? except using Wikipedia's example .

I knew That $G_1$ and $G_2$ are isomorphic, I was just wondering how to determine $G_1$ and $G_2$ are isomorphic and how we can prove $G_3$ is not isomorphic to $G_1$ or $G_2$?

$\endgroup$
1
  • $\begingroup$ Just a correction: the link that you provide mentions ways to show non-isomorphism. They are not ways to prove isomorphism as you mention. $\endgroup$ – Paresh Dec 12 '12 at 16:06
1
$\begingroup$

To add to the answer of user108903, to prove two graphs are not isomorphic, you need to find some graph property that one has but the other doesn't. Sometimes this is easy and sometimes this is not (sometimes it's as easy as showing their degree sequences are different). user108903's suggestion here is to see which ones are bipartite. In this case, that works to show Graph 3 is not isomorphic to 1 or 2. An equivalent way would be to find the chromatic numbers of the graphs. If you look at a graph theory textbook on this subject, there will probably be a few examples where they show different ways to prove two graphs are non-isomorphic. I know Graphs and Digraphs by Chartrand, et al, does.

Another way that would work here would be to look at the independence numbers of the graphs. I think that finding the largest induced cycle would also do the trick. I believe you can find one of length 5 in graph 3, whereas you can not find one of odd order in any bipartite graph, to go back to the hint of user108903.

To show that two graphs are actually isomorphic, you need to construct an isomorphism from one to the other. So, construct a map from graph 1 to 2 that preserves adjacency/non-adjacency. There is not some finite list of properties you can check to determine if two graphs are isomorphic, as far as I know.

$\endgroup$
1
$\begingroup$

Hint: which of these graphs are bipartite?

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.