DM-Graphs-Q5

+3 votes

Which of the following graphs are isomorphic?

(A). Graph 1 and Graph 4

(B). Graph 2 and Graph 3

(C). Graph 1 and Graph 3

(D). Graph 2 and Graph 4

asked Jul 12 in Discrete Maths by gbeditor (23,750 points)
reshown Jul 13 by gbeditor

2 Answers

+1 vote

(B). Graph 2 and Graph 3

(C). Graph 1 and Graph 3

I think both are right.

@Kiran sir, please verify

Reference: http://mathworld.wolfram.com/WagnerGraph.html

answered Jul 14 by lakshmanpro20 (6,330 points)
edited Jul 14 by lakshmanpro20
but same degree sequence does not imply that they are isomorphic.
Not having same degree implies that they are not isomorphic

p --> q   is not eq. to its inverse   ~p --> ~q

therefore graph 4 is out of question, but how to differentiate between the graphs 1,2,3
Yes, you are right, I'm trying to find a number of cycles.
I also agree
@Kiran sir please correct it where I'm wrong?
bro in graph 4 f and h both have degree 4
if anyone wants to join our discussion group
https://chat.whatsapp.com/KioGCcB8oSIHF17pElhyYZ
0 votes
heres an easy solution

A) 1 and 4 are not isomorphic (iv has 3-length cycle but i does not)

D) similarly 2 and 4 are not isomorhic(ii does not have 3-length cycle)

C) also 1and 3 are not isomorphic( iii has 5-length cycle which is absent in i)

so A,C,D are are wrong, remaining is B which must be the answer. comment if you find any thing wrong
answered Aug 25 by tsabhineetsingh192 (4,160 points)
@tsabhineetsingh192 i think (i) has cycle of length 5 h-a-b-c-d-h
I think (i) and (iii) are not isomorphic bcoz in (iii) there can be maximum 3 cycles of length 4 and in (i) there can be more than 3 cycles of length 4,correct me if am wrong
Yes, 1 has five length cycle. I didn't see it. Thx for pointing out
How only 3 in i) ( bcgfb ,cdhgc, deahd, efbae)
@tsabhineetsingh192 bro read my comment once again ,
"I think (i) and (iii) are not isomorphic bcoz in (iii) there can be maximum 3 cycles of length 4 and in (i) there can be more than 3 cycles of length 4"
Answer:
...