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

[@drakrool]

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!

[@angelicabattista5137]

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

[@PunmasterSTP]

Sounds like it'd be a wonderful Saturday evening!

[@thegt]

High quality way to present information! Thank you!

[@WrathofMath]

Thanks for watching!

[@48_subhambanerjee22]

my goto teacher for Graph theory

[@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

[@nishabaruwal8285]

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

[@WrathofMath]

So glad to help and 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.

[@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!

[@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!

[@basedneeble7350]

Perfect explanation thenk you, exam...saved

[@WrathofMath]

Thank you, I am glad it helped!

[@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!

[@mukeshpajiyar3507]

appreciative explanation sir

[@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

[@saisskumar1502]

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

[@WrathofMath]

The best plan!

[@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

[@judepope6196]

amazing explanation

[@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

[@saraeskandarirad3436]

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

[@WrathofMath]

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

[@037priya2]

Clearly understood tq sir👍👍

[@WrathofMath]

You're welcome, glad it helped!

[@dehilesjugurtha2072]

thank you a lot man, this helped me a lot

[@WrathofMath]

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

[@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!

[@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

[@salwam.7256]

Very good,thanks very much

[@WrathofMath]

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

[@Persian771]

The best explanation.thanks.

[@WrathofMath]

I'm glad it helped, thanks for watching!

[@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

[@Jjjj4356]

This was so useful. Thanks!

[@WrathofMath]

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

[@merxgrc9940]

lmaoooo what a wild evening that would be 4:42

[@dudeyouhavenoidea]

Beautiful saturday evening

[@WrathofMath]

It was indeed!

[@mohammadrezajavadi3498]

Well done

[@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?

[@user13443fg]

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

[@azizbekibnhamid642]

Thanks bro!

[@winm3310]

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

[@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

[@YuriLiu-n4r]

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

[@blacklight8932]

A bipartite graph has two independent sets!

[@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!

[@Fine_Mouche]

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

[@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

[@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.

[@starry1667]

Awesome !

[@WrathofMath]

Thank you!

[@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

[@iZeyad95]

THANK YOU SIR

[@WrathofMath]

You're welcome! Thank you for watching!

[@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!

[@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.

[@user-fh9wm2re2j]

Tysm!!

[@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

[@hardinrami8500]

thank you

[@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!

[@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

[@sasmitapatra1973]

Thanks sir

[@WrathofMath]

You're welcome, thanks for watching!

[@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!

[@chazy7729]

👍🏻👍🏻

[@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?

[@hajarsadoon5318]

thanks!

[@WrathofMath]

No problem! Thanks for watching!

[@judepope6196]

love it

[@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

[@saraeskandarirad3436]

thanks

[@WrathofMath]

My pleasure, thanks for watching!

[@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!

[@shreyaverma5303]

👍

[@WrathofMath]

Thanks for watching!

[@janesedin3938]

Data analysis

[@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!

[@solaceyes7767]

Ross

[@WrathofMath]

Thanks for watching!

[@exe.m1dn1ght]

Dude you lost me in the first 30 seconds

[@vaibhavilohani3421]

Thank you sir

[@WrathofMath]

No problem, thanks for watching!

[@sai2334]

Nice

[@WrathofMath]

Thanks for watching!