GATE CSE 2012 | Question: 26

Question

Which of the following graphs is isomorphic to 

 

• A.
  
• B.
  
• C.
  
• D.
  

Comments

That was an upload issue; option A is now corrected.

---

Video Explanation: https://youtu.be/uBCjHOM_iFU 

---

nice explaination sir

Answer 1

For these type of questions find which are not isomorphic.

The graph in option (A) has a $3$ length cycle whereas the original graph does not have a $3$ length cycle
The graph in option (C) has vertex with degree $3$ whereas the original graph does not have a vertex with degree $3$
The graph in option (D) has a $4$ length cycle whereas the original graph does not have a $4$ length cycle

so option B must be correct.

Comments

Faster way: in question a node with degree 4 is adjacent to nodes having degree 2,2,2,1. only b satisfy the answer.

Why to check like this?

In isomorphism we map vertices such that adjacency is preserved.

---

Can we say if the degree sequence matches then its isomorphic ??

---

@Rohit0911 we cannot say that, isomorphism also depends on other factors beside degree sequence such as presence of cycles, connectivity and so on. In the given question as well B and D have the same degree sequence but they are not isomorphic.

Answer 2

Ans: (B)

Explanation: Degree sequence of the given graph 4-2-2-2-2-2-1-1.

Degree sequene for other options: 

     A) 4-3 failed

    C)  3- failed

    For B) and D) degree sequence matches with given 4-2-2-2-2-2-1-1. Comparing B) , D) and original graph: original graph has 5-cycle. But D) have only 4-cycle. 

    B) matches all the criterias for isomorphic graph.

Comments

Good explanation.Thanks

Answer 3

if graphs have to be isomorphic then they must follow the three condition

(1) no of points must be same

(2) no of edges also must be same

(3) degree sequence must be same

if these three conditon is following simultaneously then graph will be isomorpphic

option b is correct

Comments

Those are Necessary Conidtions and Not Sufficient to decide whether two graphs are Isomorphic.

---

Isomorphic graph: Two graphs are isomorphic if there is one-to-one correspondence between them which preserves the Incidence relation.

if graphs have to be isomorphic then they must follow the 4 condition 
(1) no of vertices must be same 

(2) no of edges also must be same 

(3) degree sequence must be same 

(4)Incidence relation must be preserves

---

@warrior 
What does it mean by incidence relation ?

Answer 4

For Isomorphic :i)No of edges must be same ii)No of vertices must be same  iii)And Pendant vertex same too

all options have equal number of edges and vertices but the thing which differ it from right one is pendant vertex

In given graph a node which have pendant vertex is 4 and 1 vertex has 2 nodes and another is one so option B contains same so option B is right one