Log In
22 votes

Which of the following graphs is isomorphic to 


in Graph Theory
edited by

Things to note about the structure of the initial graph.

  • a cycle of length 5
  • have 1 and 2 length line attached to the same vertex.

(A) No cycle of length 5

(C) line graph of length 1 and 2 attached to a different vertex.

(D)  No cycle of length 5

I think the answer should be option (A) and option (B) both.

As option A looks just the same as the given graph in the question and option B is following all the graph-theoretic properties.

Therefore the answer is Option A and B.

Please correct me if I am wrong.
That was an upload issue; option A is now corrected.

4 Answers

37 votes
Best answer

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.

edited by
sir can we do in this way

in given graph we have one 4 degree vertex delete that vertex obviously now  we will have to delete all the adjacent edges to that 4 degree vertex,repeat thesame process in the (b) option.

after that check that both the graph are same or not both graph are same therfore they are isomorphic!!

A Quicker Solution is

* Degree Sequence of Option A and C are not as same as the Given Graph. So can be eliminated

* In Option D vertex with degree 4 is adjacent to vertices with degrees {2,2,2,2} whereas in the given graph it is (vertex with degree 4) adjacent to vertices with degrees {1,2,2,2 } so option D can also be eliminated.

* Option B satisfies all necessary conditions and also also has a one to one corresspondence with the given graph.

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.
7 votes

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.

Good explanation.Thanks
4 votes
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

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


What does it mean by incidence relation ?

2 votes
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

Related questions

3 votes
2 answers
Are the two digraphs shown in the above figure isomorphic? Justify your answer.
asked Dec 20, 2016 in Graph Theory jothee 479 views
30 votes
6 answers
A cycle on $n$ vertices is isomorphic to its complement. The value of $n$ is _____.
asked Sep 28, 2014 in Graph Theory jothee 8.7k views
0 votes
2 answers
State whether the following statements are TRUE or FALSE: Every infinite cyclic group is isomorphic to the infinite cyclic group of intergers under addition.
asked Nov 9, 2016 in Graph Theory makhdoom ghaya 500 views
83 votes
8 answers
Let $G$ be a complete undirected graph on $6$ vertices. If vertices of $G$ are labeled, then the number of distinct cycles of length $4$ in $G$ is equal to $15$ $30$ $90$ $360$
asked Sep 12, 2014 in Graph Theory gatecse 19.2k views