What is a Bipartite Graph? | Graph Theory

[@WrathofMath]

Support the production of this course by joining Wrath of Math as a Channel Member for exclusive and early videos, original music, and upcoming lecture notes for the graph theory series! Plus your comments will be highlighted for me so it is more likely I'll answer your questions! kzbin.info/door/yEKvaxi8mt9FMc62MHcliwjoin Graph Theory course: kzbin.info/aero/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH Graph Theory exercises: kzbin.info/aero/PLztBpqftvzxXtYASoshtU3yEKqEmo1o1L

[@coleabrahams9331]

Pro tip. When attempting to determine whether a graph is bipartite or not, if two vertices are connected by an edge, due to the definition of a bipartite graph, these two vertices have to be in different sets, and thus, you can colour code them differently. Continue this trend through the graph. If you find a contradiction where two vertices that are connected by an edge are of the same colour, then the graph is not a bipartite graph. Similarly, the opposite can be said to claim that a graph is bipartite.

[@WrathofMath]

Thanks for watching and great comment, that's definitely the fastest way I can imagine doing it by hand!

[@nijuyonkadesu]

wew! nais vro

[@momade986]

I usually never comment on anything. But your trick works like "magic". It is really funny how fast you can determine what a bipartite graph is!

[@edwardliu5453]

legend, thank you for sharing this

[@_Ryano]

I can't picture this in my head unfortunately. I don't understand this tip at all

[@vmudreamer]

Those must be some pretty wild and exciting Saturday evenings you must have...

[@WrathofMath]

The wildest!

[@TinyMaths]

Wow. Thanks for making this so clear. I thought I was missing something in how you can 'see' that a graph is bipartite. I could do that, but seeing it drawn out as two disjoint sets made it easier to grasp conceptually.

[@WrathofMath]

Thanks a lot for watching, I am so glad it helped!

[@thegt]

High quality way to present information! Thank you!

[@WrathofMath]

Thanks for watching!

[@pavithrapavithra2107]

Dear sir, thank you so much for teaching me this hard subject in a very understandable way..please keep it up!

[@WrathofMath]

It is my pleasure, thanks for watching! If you're looking for more graph theory, be sure to check out my graph theory playlist! kzbin.info/aero/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

[@angelicabattista5137]

Thanks, this explanation was way better than my professor’s one!

[@nishabaruwal8285]

amazing no one could have described in a more better and understanding way

[@WrathofMath]

So glad to help and thanks for watching! :)

[@jingyiwang5113]

Thanks for another amazing video explaining a crucial part of graph theory! It is really helpful to me!😀

[@WrathofMath]

Awesome, thanks for watching!

[@chazy7729]

Oh now I understood this topic.. :-)

[@WrathofMath]

Glad to hear, thanks for watching!

[@LaurenAnne6]

Ooo, this would be a fun puzzle to solve for a D&D campaign! I am so going to mention this to my DM. We're a group of computer scientists and physicists. Definitely our kind of fun.

[@Gismho]

Excellent as usual. Could you also compose a video on the Bipartite Theorem, i.e. "graph is bipartite iff there are no odd cycles". Whilst the first part is straight forward, I find the second part of this theorem somewhat difficult to visualise/understand, i.e. proving that if there are no odd cycles, then graph is bipartite. Just a thought!

[@WrathofMath]

Thank you! That is a great suggestion, I'm on it!

[@WrathofMath]

Here is the proof video! It was good fun, thanks for the request! kzbin.info/www/bejne/lYWsopusebdrerM

[@PunmasterSTP]

Sounds like it'd be a wonderful Saturday evening!

[@winminaye4571]

If l, m and n are integers such that 0< l

[@basedneeble7350]

Perfect explanation thenk you, exam...saved

[@WrathofMath]

Thank you, I am glad it helped!

[@vinsmokesanji175]

Sir..So in bipartite graphs is it not necessary to a one edge from the one set should connect to every edge from the other set?

[@vaibhavilohani3421]

Thank you sir

[@WrathofMath]

No problem, thanks for watching!

[@user13443fg]

what if there is an edge between nodes in same set along with edges to other set, is it bipartite?

[@tongpoo8985]

challenging your friends to solve a bipartite graph. you absolute madlad ;^)

[@WrathofMath]

People always tell me I know how to have a good time!

[@saisskumar1502]

Graphs on a Saturday? Sounds like a plan!! ;)

[@WrathofMath]

The best plan!

[@mohsinaliirfan2186]

Thank u soo much for explaining so well, love and Repect from Pakistan

[@WrathofMath]

You're very welcome, I am glad it helped and thanks for watching!

[@VinodKumar-mo1vp]

I have a labeled Bipartite graph G = ( V, E ), V = (X,Y), i need to perform clustering on X based on the E(labels). Which algorithm can be used. Could you suggest some resources.

[@Fine_Mouche]

so mathematical object "function" is a particular case of bipartite graph ?

[@mukeshpajiyar3507]

appreciative explanation sir

[@YuriLiu-n4r]

Does the number of vertexes have to be even in order for it to be bipartite

[@judepope6196]

amazing explanation

[@riveraeduardo3184]

Hello. In the case that we're presented with an unlabeled graph as in the last example, how would you determine how to label the graph to check if it is bipartite? Thank you!

[@WaronaBontsi-i2l]

label it yourself and partition it

[@shivamssharma5]

Thank you i am scared of math's wrath 👍🙏💯🔥

[@WrathofMath]

Thanks for watching! No need to be scared, - with your mind, pencil, paper, and the entire internet and textbooks at your feet! You will know all you need! Check out my playlist if you're looking for more graph theory! Good luck! kzbin.info/aero/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

[@saraeskandarirad3436]

how a hard can be an easy ! thank you very much

[@WrathofMath]

Thanks a lot for watching! I am glad it helped :)

[@salwam.7256]

Very good,thanks very much

[@WrathofMath]

You’re very welcome, thanks for watching! Let me know if you have any video requests!

[@moayyadarz2965]

ı really like your way of handling these subjects all the best

[@WrathofMath]

Thanks for watching and I'm glad you're finding the lessons helpful! :) Wishing you all the best as well!

[@Persian771]

The best explanation.thanks.

[@WrathofMath]

I'm glad it helped, thanks for watching!

[@0001-exe]

Thank you so much! I finally understand them!

[@WrathofMath]

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

[@mohammadrezajavadi3498]

Well done

[@lunakid12]

Nice outro music, too. (Made me sub to your other m-word channel.)

[@WrathofMath]

Haha, thank you! Let me know if you have any questions and check out my graph theory playlist for more! kzbin.info/aero/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

[@dehilesjugurtha2072]

thank you a lot man, this helped me a lot

[@WrathofMath]

You're very welcome, I am glad it helped!

[@limkaixin1]

Well explanation! Thank you!!

[@WrathofMath]

Thanks for watching, Kai! So glad it helped, and if you're looking for more graph theory - check out my graph theory playlist: kzbin.info/aero/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

[@akavyascv0415]

Sir for a given vertices how many biparatite graph can be draw is any formula to find out

[@WrathofMath]

Thanks for the question, and it depends! Do you mean labeled bipartite graphs? If so, the problem has a fairly straightforward solution, which I may do a lesson on soon. If you asking about unlabeled bipartite graphs (so we would be counting the bipartite graphs that are distinct up to isomorphism), the problem is a good deal more tricky, and I am not sure if there is such a nice formula for it.

[@dudeyouhavenoidea]

Beautiful saturday evening

[@WrathofMath]

It was indeed!

[@037priya2]

Clearly understood tq sir👍👍

[@WrathofMath]

You're welcome, glad it helped!

[@Jjjj4356]

This was so useful. Thanks!

[@WrathofMath]

Glad to hear it, you're welcome and thanks for watching!

[@azizbekibnhamid642]

Thanks bro!

[@omarfarhat7479]

Thank you very much

[@WrathofMath]

My pleasure, thanks for watching! If you're looking for more graph theory, check out my graph theory playlist: kzbin.info/aero/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH Many more lessons coming and let me know if you have any video requests!

[@meetpatel8519]

Is every null graph having n>=0 vertices a bipartite graph?

[@WrathofMath]

Thanks for watching and for the question! Assuming that by null you mean "no edges", then you can easily answer that question for yourself with this theorem: kzbin.info/www/bejne/lYWsopusebdrerM

[@syifaqurratuaini]

can i ask? how to choose who is A1 A2 A3 B1 B2 B3?

[@gopnikboy]

No we dont ask questions at wrath of math.

[@janesedin3938]

Hey, could u make a video abt cpa

[@Kevin_Guo]

Could you relink the donation link, please? Thanks for the great content. Would love to help with future videos by supporting your channel.

[@WrathofMath]

Thank for watching, Kevin, and I really appreciate the consideration! Here is the link to PayPal for a one time donation: www.paypal.com/donate/?token=g1RCzmhS9oEgv5e72TMhb85ixTba-jQznf2elAcIdevLFsoM6SFpvaFRoOV9C3TQatAA0G&country.x=US&locale.x=US And here is a link to Patreon for monthly donations: www.patreon.com/join/wrathofmathlessons#no_universal_links Any and all donations are very appreciated, and I’ll continue to provide the best lessons I can!

[@Winchester_1967]

Hey I know that one way to determine if a graph is bipartite is by making sure its chromatic number is 2; but I also want to know how to do it by hand. In that case, how do I know how to EXACTLY partition the vertex sets? Also, I have a question; kzbin.info/www/bejne/ioerfWqbobOgb9U --> When I coloured the second graph in this video, it didn't have a chromatic number of 2. Could someone please explain?

[@sargiskh]

isn't easy to say that graph is bipartite if it can be colored with 2 colors?

[@WrathofMath]

Yes, absolutely! For people familiar with graph coloring, that is a very nice way to describe bipartite graphs, thanks for adding that!

[@hardinrami8500]

thank you

[@merxgrc9940]

lmaoooo what a wild evening that would be 4:42

[@adityakantipudi]

Thanks dude.

[@WrathofMath]

Glad to help! Let me know if you have any questions, and check out my playlist if you're looking for more! kzbin.info/aero/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

[@teresa9519]

What's the song at the end and who is it by?

[@WrathofMath]

Thank you for watching! The song is called "Turn Over" and it is by me. There is no full version anywhere, but there is a link to my inactive music channel in the description if that interests you!

[@modemmod100]

can bipartite graph only be partitioned into 2 groups? thanks!

[@duedares]

Yes. Else we will have to call it tri-partite and so on :x

[@sophiecs9668]

What are some of classic graphes besides Bipartite Graph?

[@WrathofMath]

Thanks for watching and for the question, Sophie! Are you wondering about particular graphs of interest - like the Petersen Graph, or are you wondering about classic families of graphs - like Bipartite graphs, cycles, trees, and so on?

[@sophiecs9668]

@@WrathofMath Thank you for your reply! I'm a CS student and bipartite is a graph that we discuss a lot in the discrete math and have a lot of interesting applications in the real world. I'm wondering if there are other classic graphs that are similar to bipartite in the sense that they have very interesting properties having real-world applications. Thank you!

[@blacklight8932]

A bipartite graph has two independent sets!

[@iZeyad95]

THANK YOU SIR

[@WrathofMath]

You're welcome! Thank you for watching!

[@chazy7729]

👍🏻👍🏻

[@starry1667]

Awesome !

[@WrathofMath]

Thank you!

[@judepope6196]

love it

[@hajarsadoon5318]

thanks!

[@WrathofMath]

No problem! Thanks for watching!

[@saraeskandarirad3436]

thanks

[@WrathofMath]

My pleasure, thanks for watching!

[@sai2334]

Nice

[@WrathofMath]

Thanks for watching!

[@shreyaverma5303]

👍

[@WrathofMath]

Thanks for watching!

[@solaceyes7767]

Ross

[@WrathofMath]

Thanks for watching!

[@jamesang7861]

...got lost in the first minute...

[@jamesang7861]

got it in the last minute

[@WrathofMath]

Glad things turned around! Thanks for watching and if you're looking for more graph theory, check out my playlist! kzbin.info/aero/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

[@jamesang7861]

@@WrathofMath thank you!

[@ronaldcsjohnson4790]

4:41 Fun and wild for nerds, I guess. Just joking!

[@WrathofMath]

Fun and wild for nerds is fun and wild for me haha!

[@exe.m1dn1ght]

Dude you lost me in the first 30 seconds

[@sasmitapatra1973]

Thanks sir

[@WrathofMath]

You're welcome, thanks for watching!

[@janesedin3938]

Data analysis

[@lellajagadeeswar596]

Nice

[@WrathofMath]

Thank you! Check out my graph theory playlist if you're looking for more: kzbin.info/aero/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

[@lellajagadeeswar596]

@@WrathofMath ok sir