What are Isomorphic Graphs? | Graph Isomorphism, Graph Theory

How do we formally describe two graphs "having the same structure"? The term for this is "isomorphic". Two graphs that have the same structure are called isomorphic, and we'll define exactly what that means with examples in today's video graph theory lesson!
Check out the full Graph Theory playlist with over 130 videos and counting! • Graph Theory
Two graphs G and H are said to be isomorphic if there exists a bijection, f, from the vertices of G to the vertices of H such that if uv is an edge in G then f(u)f(v) is an edge in H. In other words, the function preserves adjacency and non adjacency. Saying that f is bijective means it is one-to-one (injective) and onto (surjective). Watch the full video for all the details!
SOLUTION TO PRACTICE PROBLEM:
The graphs A and B are isomorphic. Here is an isomorphism, f, between them:
f(v1) = u2
f(v2) = u5
f(v3) = u1
f(v4) = u4
f(v5) = u3
Note that this isomorphism is not unique, so you might have a different one that is also valid. Use the definition of isomorphic graphs to verify your isomorphism.
The graphs C and D are not isomorphic. The graph C has 6 edges and D has only 5. Thus, each of the 6 pairs of adjacent vertices in C could not possibly be matched to 6 pairs of adjacent vertices in D - thus there is no isomorphism.
◉Textbooks I Like◉
Graph Theory: amzn.to/3JHQtZj
Real Analysis: amzn.to/3CMdgjI
Proofs and Set Theory: amzn.to/367VBXP (available for free online)
Statistics: amzn.to/3tsaEER
Abstract Algebra: amzn.to/3IjoZaO
Discrete Math: amzn.to/3qfhoUn
Number Theory: amzn.to/3JqpOQd
I hope you find this video helpful, and be sure to ask any questions down in the comments!
********************************************************************
The outro music is by a favorite musician of mine named Vallow, who, upon my request, kindly gave me permission to use his music in my outros. I usually put my own music in the outros, but I love Vallow's music, and wanted to share it with those of you watching. Please check out all of his wonderful work.
Vallow Bandcamp: vallow.bandcamp.com/
Vallow Spotify: open.spotify.com/artist/0fRtu...
Vallow SoundCloud: / benwatts-3
********************************************************************
+WRATH OF MATH+
◆ Support Wrath of Math on Patreon: / wrathofmathlessons
Follow Wrath of Math on...
● Instagram: / wrathofmathedu
● Facebook: / wrathofmath
● Twitter: / wrathofmathedu
My Music Channel: / seanemusic

[@WrathofMath]

Check out the full Graph Theory playlist with over 130 videos and counting! kzbin.info/aero/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

[@ehza]

Thanks

[@samerkia]

First 50 seconds already told me more than a 16 page section in a math book... thank you sir.

[@WrathofMath]

You're very welcome and thank you! I am glad it helped and let me know if you ever have any questions!

[@yongkangchia1993]

verbose topic xD

[@jomama3465]

Now pass an exam with only this video as guide.

[@momcity7819]

i like the speed of teaching , very precise ,very clear and to the point with revision.....omg..

[@WrathofMath]

Thanks so much! I am glad it helped and let me know if you ever have any questions!

[@xayvon3788]

I love how easily you simplified the concept by breaking it down into further smaller topics. You are insane

[@tomasalves5182]

this is by far the best video on this topic available on the internet

[@WrathofMath]

Thanks so much!

[@sandeepmehta4487]

Thank you for taking the time to share your knowledge. Graph C & D are not isomorphic since the number of vertices are not same. Graph A & B are isomorphic as they have same number of vertices and edges, the degree of each of the vertices in both graphs is same ( 2 ) and a bijective function linking both the graphs is possible.

[@WrathofMath]

Thanks for watching and right on! Graphs A and B have the same number of vertices and edges, and the same vertex degrees, which isn't enough to conclude they are isomorphic, but it does suggest they might be. Then, as you said, a bijective function exists between the graphs that preserves adjacency and nonadjacency. I believe I typed out an example of such a bijection in the description for anyone curious.

[@yagizsen113]

@@WrathofMath are all complimentary graphs isomorphic as well?

[@alisolhjoo3201]

Thanks for taking time to teach us the difficult subjects in a simplified way

[@WrathofMath]

Glad to help!

[@hayleyhendry4018]

This is by far the best explanation I’ve come across. I have autism and memory issues which interfere with my ability to understand abstract concepts and picture things like this in my head. Your use of plain English words and examples really helped!

[@aviancrane]

This helped me with understanding people that don't speak in plain English: Analogies that correctly communicate an idea are isomorphic to the idea. Analogies that fail to communicate an idea are not isomorphic. Sus out the objects (the vertices) and the relationships (the edges) and then map their analogies to the plain english that makes sense to you. Then communicate your version back to them. If they confirm your version is the same as theirs, then the isomorphism has been achieved and the idea has been communicated.

[@redvik2219]

Thanks for this. Been trying to understand this thing for a week now and now I finally got it

[@WrathofMath]

Awesome, glad it helped! Thanks for watching!

[@asthaghosh9108]

Well that was a brilliant explanation..easy to understand . A and B are isomorphic ( because same number of vertices and there are exist bijective function as well) While C and D are non isomorphic (As it doesn't have same number of vertices and and bijective function is not possible.)

[@jinmeigao6561]

Thank you! it is really a good vieo. you explained very clearly. I think Graph A and B is isomorphic, because 1.They both have 5 vertices and 5 edges 2. each of their vertices has two adjacencies V(A)→ V(B) 𝜑 v1 v2 v3 v4 v5 u1 u4 u3 u2 u5 so they are bijective 3. v1 v2 ∈E(H) and 𝜑 (v1)𝜑 (v2) ∈E(H) For graph C and D, they are not isomorphic, because they don't have same vertices and edages

[@fazilapatel2499]

As always, thank you for your informative videos :)

[@WrathofMath]

My pleasure! Thanks for watching! :)

[@amanmahato3897]

You have the beauty of symplification I has been looking for 🙏

[@WrathofMath]

Thank you! I try to make concepts as clear as I can. If you're looking for more graph theory, check out my playlist! kzbin.info/aero/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

[@chidochiradza]

a work of art, you deserve my tuition

[@HopefulMathGirl]

Thank you for this easy and wonderfully explained video.

[@WrathofMath]

So glad to help! Thanks for watching, and if you're looking for more graph theory check out my playlist! kzbin.info/aero/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

[@saifalisaif8144]

thank you so much for this nice explanation now i knew how isomorphic work by easy way

[@WrathofMath]

So glad it helped, thanks for watching! Check out my graph theory playlist if you're looking for more: kzbin.info/aero/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH Lots of lessons left to come!

[@masudurtawhid792]

You have become one of the best teacher in my list of the best teachers

[@WrathofMath]

Thanks so much, Masudur! I do my best, and I'm so glad you've found my explanations helpful. If you're looking for more graph theory, check out my playlist, and let me know if you ever have any questions! kzbin.info/aero/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

[@normmacdonaldfan]

This video hits different. Keep it up!!!

[@WrathofMath]

Thank you! Be sure to check out my Graph Theory playlist if you haven't many more lessons to come! kzbin.info/aero/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

[@patrickgeyer9239]

Brilliant video. Thank you!

[@WrathofMath]

Thank you! So glad it helped, this is one of my favorites.

[@guahym]

Very easy to understand❤❤❤❤ love this video

[@dorcasmiriko6799]

Thanks alot for the knowledge..... It's easy to understand ur explanations

[@WrathofMath]

My pleasure, thanks for watching!

[@mostakmahmudchowdhury6673]

Execelent explanation bro.I understood each and every word.Thanks for the video

[@WrathofMath]

Glad to hear it, thanks for watching!

[@seanconnors3356]

Watched another video on this and determined I would have to study various abstract theories to get to the point of understanding isomorphism (since I looked this up due to php coding not from mathematical theory) then found yours and it made sense. TY!

[@WrathofMath]

So glad it helped, thanks for watching!

[@silkinana6625]

Thank you very much for this video. It was really useful, and simply explained. It helped me to fill the gaps at this point. Thanks again

[@WrathofMath]

Glad to help! Thanks for watching!

[@damienpace72]

Loved this video, thank you very much! I wish my Discrete Math teachers had the ability to explain things like you.

[@WrathofMath]

So glad you liked it, thanks for watching! If you're looking for more graph theory, check out my playlist! kzbin.info/aero/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH I will make a discrete math playlist at some point, but for now there is plenty of graph theory!

[@Bob50520]

Clean explanation. Very nice.

[@WrathofMath]

Thank you! Glad it was clear!

[@HexViccissitude]

The music at the very end scared the shit out of me it sounded like it was coming from outside of my headphones at first. Thank you for your explanation here I am going to use it to help me on my Algorithms and Data Structures homework

[@WrathofMath]

Thanks for watching and I am glad it helped! And haha, sorry about the scare with the music!

[@ThantSinAung-ud4yx]

Crystal clear explanation than my over priced university lecture.

[@dastanaskarbekov7190]

Thank you! It really helped.

[@ramshashaikh5165]

Thank you so much Sean. Your lectures are really helpful. You convey everything properly in a very short time. I can listen to your lectures all day and won't get tired😂 Can you please make a video on Arboricity, linear arboricity and related topics/Theorems like Nash-Williams theorem!?

[@WrathofMath]

Thanks so much for watching, Ramsha! There is still a lot of graph theory for me to cover to complete this playlist, but I am glad it has been helpful. I'd love to cover that stuff, unfortunately it would take a while and is a very niche topic. I can't really justify the time for it right now, but if you have any specific questions on that material feel free to shoot me a message!

[@ramshashaikh5165]

@@WrathofMath it’s good to hear back from you within 48 hours😊 I am actually studying this topic currently but your lecture on this would have been of great help. I revised and learned almost all GT basics from your videos. I understand you must be busy. I will surely ask for help whenever needed. Thank you so much. God bless you🌻

[@ramshashaikh5165]

@@WrathofMath arboricity of a graph is actually minimum number of forests into which its edges can be partitioned. But I want to understand that partition through some examples. How do we do partition of a graph into forests!? What would be the rules to follow here!? Please answer for them whenever you have time. Tc😊

[@aleksandarbosnjak9688]

beautiful explanation, thanks!

[@WrathofMath]

Thanks for watching!

[@joe_hoeller_chicago]

GREAT video! Thank you.

[@WrathofMath]

You are welcome! Thanks for watching!

[@DanielSColao]

Great video, keep it up!

[@mocha_genie7416]

AMEN to you my guy! First few seconds and, VOILA! MAGIC!

[@WrathofMath]

So glad it helped!

[@Felicity-wy6fj]

Amazing Video,Thank youuu❤

[@WrathofMath]

You're welcome, thanks for watching!

[@janestefan7920]

Thank you sir. Great channel!

[@WrathofMath]

Thank you Jane! I do my best, let me know if you ever have any video requests!

[@kylepalmer6936]

Would you please make a vide on the differences between automorphic, isomorphic, and homomorphic graphs?

[@rohanthomas5434]

A and B are isomorphic, phi: map v1 to u2, v5 to u3, v4 to u4, v3 to u1, v2 to u5. Sort of pick any vertex and follow the pack where it‘s edges takes you.

[@anabildebnath2590]

So helpful!!

[@WrathofMath]

Glad to hear it, thanks a lot for watching! If you're looking for more graph theory, check out my playlist! kzbin.info/aero/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

[@boulevardepo6587]

Thank you sirr, well explained

[@WrathofMath]

Thank you!

[@levvillanueva9047]

Thank you. Well explained (y) A and B are isomorphic because if you can unfold the star and you get the same structure (visually) as the pentagon. C and D are not isomorphic, there's not vertex with 4 edges in D, so there's a pare of vertices that will be adjacent in C but not D.

[@williamcarr8234]

that was a really good video tysm

[@WrathofMath]

Glad to help!

[@alexanderwolf3335]

great video, thanks for getting me through my discrete maths course xd

[@WrathofMath]

Haha, glad to be able to help! If you haven't already, check out the graph theory playlist: kzbin.info/aero/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH Everything is pretty well organized in it for your convenience. I'll be making a general discrete math playlist eventually, but it will take time! Let me know if you ever have any video requests!

[@mahmoudadelelkholy3130]

thanks u very much Mahmoud from Egypt

[@WrathofMath]

You're very welcome! Thanks for watching, Mahmoud!

[@emanuelegiacomuzzo5859]

Sweeeeet, great explanation.

[@WrathofMath]

Glad it was clear, thanks for watching!

[@arishkhan6786]

Nice demonstration

[@WrathofMath]

Thanks, Arish!

[@epistemicompute]

Thank you for the explanation. What is the exit music? It sounds really good!

[@epistemicompute]

I know it's one of Vallow's songs, but which one?

[@yongchaojia4610]

very clear, thx

[@WrathofMath]

Glad to help!

[@gusforyou]

could you do more on motifs?

[@IoniB]

THANK U SO MUCHHHH

[@sadingsadin]

you are the best!

[@5yalz50]

Thank you so much I love you man❤️❤️❤️❤️

[@WrathofMath]

Much love back! Thanks for watching and let me know if you ever have any questions!

[@Freedomind901]

A policeman (red diamond) runs after a thief (green square) in the diagram above according to the following rules: • The 2 players are obliged to move in turn; • The policeman moves first; • A player can only move following an arc, and he can only move from a distance from a peak of its original position; • The policeman seeks to catch the thief (that is to say that the 2 are on the same summit) a) Find a strategy for the police to catch the thief. b) Explain why the strategy works all the time

[@djtygre]

thank you! damn you talk through this like a boss!

[@WrathofMath]

My pleasure! So glad it helped!

[@djtygre]

@@WrathofMath Can you do a video on strong induction and non-homogenous recurrence relations? I love the way you explain everything. I have a really hard time understanding these two concepts.

[@barsboldulziisaikhan8997]

how did you teach such that? it was crazy and easy to understand, ty sir

[@CuriousAnonDev]

video request : maximum matching and max flow algorithm in bipartite graph

[@yolo8141]

Could you please make an effort on Optimal profix code problems? Thanks

[@PMA_ReginaldBoscoG]

I watched a video of @sarada_herke about finding isomorphism between two graphs using their adjacency matrices but I still have a doubt about finding the correct permutation matrix since there are n! distinct permutation matrices for a graph with n vertices. Please help me with this problem.

[@itech40]

Video idea (Please :D :D): applications of Isomorphic graphs inC omputer science

[@tarvez0576]

COuld you please teach Degree distribution and power law

[@amirghorban2044]

Nice like always God bless you

[@WrathofMath]

Thank you very much! Let me know if you ever have any video requests!

[@korrapolusita5244]

Is there possible of self loop in isomorphic graphs

[@eshaanbagga5159]

Easy to understand....

[@nawarzarifeh5339]

Thank you Sean for the great explanation! So if a maximum degree between 2 graphs differs then they are not isomorphic right? another question if the longest path of the first graph has different length from the longest path in the second graph then they are not isomorphic?

[@WrathofMath]

Thanks for watching and that's exactly right! All those sorts of properties that don't depend on the names of the vertices will be present among isomorphic graphs. If G and H are isomorphic, and G has a vertex v, with G's maximum degree of 5, then the image of v in H under the isomorphism must have just as many neighbors, and thus the same degree. Say the isomorphism is f, and so the image of v in H is f(v). Then the neighbors of v in G will necessarily have images in H that are all adjacent to f(v). More detailed explanation: kzbin.info/www/bejne/mGireayed8eigc0

[@sushobhannayak6905]

Can you do a video on matrices in graph theory

[@tarirocoffee5026]

Greate tut, thanks

[@WrathofMath]

My pleasure - glad to help!

[@Freedomind901]

hi is it possible to help me with this question please? i ve been thinking about it for a week and i m blocked

[@vikramtete7461]

Sir...One more doubt....In the graph C( bow graph), Can we say vertex a and vertex c are adjacent vertices?

[@younessradi8403]

no!,no edge betwwen them

[@Charles-xc6sr]

Dude, Can ya make a video on Automorphism. It would be helpful.

[@WrathofMath]

Thanks for watching and for the request Charles! I'd love to make a video on automorphisms soon, but no promises! If you haven't already, check out my graph theory playlist for more! kzbin.info/aero/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

[@karanbais1843]

Thank you

[@WrathofMath]

You're welcome! Thanks for watching!

[@leilenah]

nice, thanks

[@WrathofMath]

My pleasure!

[@juanb6570]

i have a doubt in regards to the A and B pair of examples in the end, i believe that they are not isomorphic because, yes, they have the same number of vertices and edges, but it doesnt preserve adjacency correctly, in A v1 and v2 are adjacent to each other and in B they aren't, there are some other cases of that in those graphs.This is assuming that the isomorphisim takes the vertices v1 to u1, v2 to u2, so on and so forth. I hope i´m okay on that observation.

[@WrathofMath]

Thanks for watching and for the question! I'm not sure what you mean by "it" doesn't preserve adjacency correctly. What is "it"? Remember in order for graphs A and B to be isomorphic, there must be an isomorphism between them, and that's the thing preserving adjacency. So, to be sure that A and B are isomorphic, we need to find an isomorphism between them, but I simply drew the graphs on screen and did not provide an isomorphism. So the exercise is to either determine they are not isomorphic and a reason why, or if you think they are isomorphic, to find an isomorphism between them. The vertices of A are labeled v1 through v5, and the vertices of B are labeled u1 through u5, but there is no isomorphism given. Does that make sense?

[@leavefeardomath]

Please make a detailed video on petersen graph. Especially I'm getting trouble to understand it properly from the book by Douglas B. West, page 13.

[@WrathofMath]

Thanks for watching and the request! I'm looking at the book, it has some cool stuff on the Petersen graph, I'll make some videos on some of it! Currently I don't have much time to do all the prep for longer detailed lessons, which require a lot of organization of ideas. But I'll do what I can!

[@leavefeardomath]

@@WrathofMath thanks a lot

[@anglebaby2010]

how do we determine the graph isomophism falls under P or NP?

[@yuriakahumanity]

This question requires more information. In reference to what?

[@keldonchase4492]

Injective means One-To-One. Surjective means Onto. At 5:18 in the video, you say that "Injective" and "Surjective" combined implies a One-To-One correspondence but One-To-One is only associated with "Injective". It is true that the graph is One-To-One and Onto but I don't think the combination of "Injective" and "Surjective" means "One-To-One". Only the "Injective" is required for "One-To-One." The "Surjective" is not necessarily required for "One-To-One". Is this a mistake in the video or am I missing something? Please advise, thank you.

[@WrathofMath]

Great question! It is confusing, but this is how the phrases are used. Everything you said is right, but one to one correspondence is different from one-to-one. Injective: One to one (each one input has its own one output, not shared by any other input) Surjective: Onto (the function maps the domain onto the entire codomain, every element of the codomain gets mapped onto by some domain element) Bijective: One-to-one correspondence (the domain and codomain correspond exactly - one to one - every domain element corresponds to one codomain element and vice versa) Hope that helps!

[@keldonchase4492]

@@WrathofMath That makes perfect sense. I had clumsily assumed One-To-One and One-To-One Correspondence were the same thing. Thanks so much for the explanation and the playlist!!

[@odaakeenya]

long live to geniuses. you made life easier for me

[@WrathofMath]

So glad to help with such an important topic! Thanks for watching and check out my graph theory playlist if you're looking for more! Thanks for watching, graph theory can indeed be hard! Let me know if you have any questions I can help clear up, and check out my playlist if you're looking for more graph theory videos that may solve some of your problems: kzbin.info/aero/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

[@vartikasingh9618]

Where are you from?

[@mangai3599]

Solution to P1: Answer: Yes, they are Isomorphic. Proof: Since |V(A)|=|V(B)|, so there may a bijection. We give a construction. Let a function ϕ: V(A) → V(B) such that ϕ ( v1)=u2, ϕ (v2)=u5, ϕ(v3)=u1, ϕ(v4)=u4, ϕ(v5)=u3. We see this is clearly a bijection. Hence, A and B are Isomorphic. ⬛ Solution to P2: Answer: No, graph C and D are not Isomorphic. Proof: Observe |V(A)| ≠ |V(B)|, hence there is no bijection from V(B) to V(C). So the C and D are not Isomorphic.⬛ Thanks for the video.😀

[@raveenaashree4809]

Can you explain about automorphic graphs

[@WrathofMath]

Thanks for watching and the request! Do you mean graphs that have a non-trivial automorphism?

[@raveenaashree4809]

@@WrathofMath yes!

[@aviancrane]

A & B are isomorphic: 5 verts, all verts have 2 edges, both graphs have 5 Hamiltonian Circuits each with 5 steps. C is not isomorphic to any because it has a vert with 4 edges while no other graph has a vert with 4 edges. D is not isomorphic because it has 4 verts while all others have 5 verts.

[@vatitopatitopotitopolitopo4918]

you're af ucking legend

[@WrathofMath]

Thank you, I do my best!

[@Ben-nu9mj]

better than the lecturer im paying 9k for

[@WrathofMath]

That's too bad - but I appreciate it!

[@15997359]

Bijection is 1to1 unto correspondence

[@WrathofMath]

Yes it is!

[@liquiddonkey6530]

"But officer, I thought it was okay to go through the red light; it has the same one-point structure as the green light."

[@Freedomind901]

here is the graph image imgur.com/a/66nkvl7

[@vikramtete7461]

A and B are isomorphic graphs

[@PunmasterSTP]

Isomorphic graphs? More like "Incredible knowledge that gets"...you good grades on tests!

[@vamshikrishna5348]

1 and 2 are isomorphic

[@tsunningwah3471]

rddd

[@fazilapatel2499]

Graphs A and B are isomorphic but C and D are not.

[@WrathofMath]

Right on, good work!

[@jinhuang2417]

A B are isomorphism, but CD not

[@Y747Y]

The so called “isomorphic” in simple words is Invertible Linear Transformation.

[@jrinfo7103]

Sir 😂 i just came to ur video to clear the last sum but u didn't do that and leave to us

[@DonaldMurf]

Is this Demetri from Cobra Kai?

[@WrathofMath]

If it is would you subscribe?

[@liquiddonkey6530]

overweight wife/girlfriend: "Do I look fat in this?" guy's brain:

[@antoniomazilu632]

ο κολοκτρωνης με εφερε εδω