Whether the given pair of graphs is isomorphic?Pls provide a rigorous argument.

Question

Comments

https://math.stackexchange.com/questions/3493598/determine-whether-the-following-graphs-are-isomorphic-or-not

Answer 1

Two graph r isomorphic iff they have :

1. Same no of edges

2. Same no of vertices

3. Same no of particular length (i.e. 3 length , 4 length,.....) cycle..

Comments

Graph equivalence checking is NPC  problem.. no algo exist till now. U have to do by brute force method only..

---

Yeah, I see. It means here we are saying these two graphs isomorphic just because we have insufficient reasons to prove them non isomorphic.

---

can we check isomorphism of graph in this way .??

delete the maximun degree vertex in first graph and second graph again apply this argument to the resulting graph.??continue untill we get graph which looks very simple so that we can easily map one graph to another graph.??

Answer 2

1)Both graphs have equal no of vertices(10).

2)Both graphs have equal no of edges(15).

3)Both graphs have same degree sequence. 3,3,3,3,3,3,3,3,3,3

4)Each vertex in both graphs is connected to other 3 vertices of degree three

so there neighboring vertices degree is also same in both graphs(this cover the concepts of same pairs of cycles).

Hence both graph are isomorphic.