How to Tell if Graph is Bipartite (by hand) | Graph Theory

How can we tell if a graph is bipartite by hand? We'll discuss the easiest way to identify bipartite graphs in today's graph theory lesson. This method takes advantage of the fact that bipartite graphs are 2-colorable. This means their vertices can be colored using only two colors so adjacent vertices are colored differently (sometimes called a proper coloring). You may easily see that being 2-colorable and bipartite are the exact same things! #GraphTheory
Since a graph being bipartite is the same as being 2-colorable, to determine if a graph is bipartite we simply pick a vertex v to begin coloring - then assign it Color 1. If the graph is bipartite, then the neighbors of v must be colored with Color 2. We continue in this way, coloring neighbors different colors (using only two colors total) until we either finish coloring the graph or we are forced to color two adjacent vertices the same way. If two adjacent vertices are forced to be colored the same way, then the graph cannot possibly be bipartite - since we have been forced to put adjacent vertices in the same set (or color). If we are able to finish coloring the graph - then it is bipartite and we now have a bipartite partitioning of the graph into two colored sets.
Bipartite Graphs: • What is a Bipartite Gr...
Proof Graph with no Odd Cycles is Bipartite: • Proof: If a Graph has ...
Vertex Colorings and Chromatic Numbers: • Vertex Colorings and t...
Graph Theory playlist: • Graph Theory
★DONATE★
◆ Support Wrath of Math on Patreon for early access to new videos and other exclusive benefits: / wrathofmathlessons
◆ Donate on PayPal: www.paypal.me/wrathofmath
Thanks to Robert Rennie, Barbara Sharrock, and Rolf Waefler for their generous support on Patreon!
Thanks to Crayon Angel, my favorite musician in the world, who upon my request gave me permission to use his music in my math lessons: crayonangel.bandcamp.com/
Follow Wrath of Math on...
● Instagram: / wrathofmathedu
● Facebook: / wrathofmath
● Twitter: / wrathofmathedu
My Music Channel: / @emery3050

Пікірлер: 100

  • @WrathofMath
    @WrathofMath2 жыл бұрын

    If you're into Graph Theory, check out my Graph Theory playlist, with more than 150 videos and more than 100,000 views! And many more of both to come! kzread.info/head/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH If you're enjoying the Christmas lessons, please share them around - it's a huge help!

  • @santiagodiaz1707
    @santiagodiaz1707 Жыл бұрын

    Currently taking Discrete Math 2 and the textbook definition for Bipartite-ness was so verbose and hard to comprehend, but this made it so easy, thank you!!!!!

  • @WrathofMath

    @WrathofMath

    Жыл бұрын

    So glad it helped!

  • @PunmasterSTP

    @PunmasterSTP

    Ай бұрын

    I didn't even know Discrete Math could be divided up into multiple classes. What did you think of it, and did you have a favorite one?

  • @xxtuddlexx
    @xxtuddlexx6 ай бұрын

    Thanks we didnt learn this in discrete 2 at rutgers despite learning bipartite. They seem so anti visualization even when it'll obviously make things clearlier to many people.

  • @PunmasterSTP

    @PunmasterSTP

    Ай бұрын

    Oh man, I'm sorry to hear that! I can't even think about approaching graph theory in a non-visual way.

  • @martinmaulhardt9852
    @martinmaulhardt98522 жыл бұрын

    Great job, my friend. Seen many of your videos, in particular the one that you prove Ore´s theorem. Merry Christmas to you! Greetings from Argentina!

  • @godlovedimitri5149
    @godlovedimitri5149Ай бұрын

    Thanks for the explanation!!! Makes this concept clearer.

  • @juliannafotheringham7101
    @juliannafotheringham71012 жыл бұрын

    Great video such a clear explanation, thank you!

  • @WrathofMath

    @WrathofMath

    2 жыл бұрын

    Thanks, Julianna, glad to help! Check out my playlist if you're looking for more, and let me know if you have any questions! kzread.info/head/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

  • @melcomemonteiro6800
    @melcomemonteiro6800 Жыл бұрын

    Perfect explanation ,thank you

  • @JoseSanchez-vv1zd
    @JoseSanchez-vv1zd2 жыл бұрын

    Super clear explanation! Thank you for making this. 🙂

  • @WrathofMath

    @WrathofMath

    2 жыл бұрын

    My pleasure, glad it was clear! Let me know if you have any questions and check out my graph theory playlist for more! kzread.info/head/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

  • @kyusiv9026
    @kyusiv9026 Жыл бұрын

    Perfectly explained, thank you so much!!

  • @WrathofMath

    @WrathofMath

    Жыл бұрын

    Thank you for watching!

  • @erikxx2940
    @erikxx29402 жыл бұрын

    Perfect explanation. Very easy and clear. Thank you :)

  • @WrathofMath

    @WrathofMath

    2 жыл бұрын

    So glad it was helpful! Thanks for watching and check out my graph theory playlist for more! kzread.info/head/PLztBpqftvzxXBhbYxoaZJmnZF6AUQr1mH

  • @user-xe5pk5pn2u
    @user-xe5pk5pn2uАй бұрын

    Thank you, this video helped out a lot.

  • @husseinshehab7775
    @husseinshehab77754 ай бұрын

    its sad that you only have 100k subscribers , you deserve millions !

  • @WrathofMath

    @WrathofMath

    4 ай бұрын

    Thank you!

  • @VietnamSteven
    @VietnamSteven2 жыл бұрын

    that's incredibly helpful! Thank you!!

  • @WrathofMath

    @WrathofMath

    2 жыл бұрын

    My pleasure, glad you thought so!

  • @masterstroke6296
    @masterstroke6296 Жыл бұрын

    Such a Great Explanation...Thank you so much...hope you will make more and more videos for us....😊😊😊

  • @foggychild8598
    @foggychild85988 ай бұрын

    Thanks for a clear explanation. I love your christmas decorations!

  • @WrathofMath

    @WrathofMath

    8 ай бұрын

    Thank you! Also, i don't know the origin of your name - but I am very pro-frog!

  • @joe_hoeller_chicago
    @joe_hoeller_chicagoАй бұрын

    Good quick concise video that gets straight to the point for beginners. 👌🏼

  • @WrathofMath

    @WrathofMath

    Ай бұрын

    Thanks for watching!

  • @arunasadeepa2795
    @arunasadeepa2795 Жыл бұрын

    Very useful to save some time 😀 thanks for the video

  • @elizabethkourbatski6413
    @elizabethkourbatski64132 ай бұрын

    Short, simple, amazing!

  • @WrathofMath

    @WrathofMath

    2 ай бұрын

    Thank you!

  • @MusayerohBah
    @MusayerohBah6 ай бұрын

    god bless got me through homework questions that were taking me an hour to even start in a good 6 minutes. thank you!!!

  • @WrathofMath

    @WrathofMath

    6 ай бұрын

    Glad it helped!

  • @sirgreen2792
    @sirgreen27922 жыл бұрын

    Always a life saver, thanks

  • @WrathofMath

    @WrathofMath

    2 жыл бұрын

    Glad to help - thanks for watching!

  • @Corri800
    @Corri800 Жыл бұрын

    Very helpful, thank you!

  • @WrathofMath

    @WrathofMath

    Жыл бұрын

    That's what I like to hear, my pleasure!

  • @talhasardar4520
    @talhasardar4520 Жыл бұрын

    Amazing , now i can identify any graph .Thank you so much . 😀

  • @WrathofMath

    @WrathofMath

    Жыл бұрын

    Glad to help!

  • @ruruxu1475
    @ruruxu1475 Жыл бұрын

    I watched a lot of your videos。 I love you🥰

  • @Abdulmalik-ne4cd
    @Abdulmalik-ne4cd Жыл бұрын

    Such a Great Explanation. Thank you :)

  • @WrathofMath

    @WrathofMath

    Жыл бұрын

    Thank you for watching!

  • @PunmasterSTP
    @PunmasterSTPАй бұрын

    2 colorable? More like "2 good"...to us by making these outstanding lectures available for free!

  • @bbben
    @bbbenАй бұрын

    Love from Philippines! Currently taking Discrete Math for my engineering course T_T. Definitions from my e-book made it seem borderline impossible to understand without visuals. I really found your video helpful, thank you!

  • @PunmasterSTP

    @PunmasterSTP

    Ай бұрын

    Oh man, good luck in the course!

  • @irisr2904
    @irisr29049 ай бұрын

    Thankyou, it was a very clear description :

  • @WrathofMath

    @WrathofMath

    9 ай бұрын

    Thanks for watching!

  • @piyushsharda9308
    @piyushsharda93088 ай бұрын

    Thank you!

  • @karihadil8454
    @karihadil84547 ай бұрын

    I LOVE THIS TEACHER OMG

  • @WrathofMath

    @WrathofMath

    7 ай бұрын

    Thank you!

  • @saichaithrik7134
    @saichaithrik71346 ай бұрын

    one of the greatest faculty ever

  • @viveksuman9600
    @viveksuman96002 жыл бұрын

    Great video. Keep going 🙌

  • @WrathofMath

    @WrathofMath

    2 жыл бұрын

    Thank you, I will! Let me know if you have any graph theory video requests!

  • @DanielKFlomo
    @DanielKFlomo Жыл бұрын

    Thanks a lot, good explanation.

  • @WrathofMath

    @WrathofMath

    Жыл бұрын

    Glad to help, thanks for watching!

  • @bobalicious4823
    @bobalicious48234 ай бұрын

    Beautiful

  • @ayanaxhye
    @ayanaxhye Жыл бұрын

    bless you brother

  • @jakelance5786
    @jakelance57862 жыл бұрын

    Awesome!!

  • @augustineshaji5336
    @augustineshaji5336 Жыл бұрын

    Thank you sir 😍😍

  • @flimdejong2030
    @flimdejong20307 ай бұрын

    Excellent video sir

  • @WrathofMath

    @WrathofMath

    7 ай бұрын

    Many thanks!

  • @micahkatz8878
    @micahkatz88782 жыл бұрын

    Great video!

  • @WrathofMath

    @WrathofMath

    2 жыл бұрын

    Thanks Micah!

  • @mikedelta658
    @mikedelta658 Жыл бұрын

    Thank you Dear!

  • @WrathofMath

    @WrathofMath

    Жыл бұрын

    Glad to help, thanks for watching!

  • @abdelrhmanemira2480
    @abdelrhmanemira2480 Жыл бұрын

    Thanks a lot

  • @WrathofMath

    @WrathofMath

    Жыл бұрын

    Glad to help!

  • @As-dk5ig
    @As-dk5ig Жыл бұрын

    I can’t think you enough 😢❤

  • @xanderpeter5326
    @xanderpeter5326 Жыл бұрын

    god bless you mahn!!!!

  • @luziasouza6688
    @luziasouza668810 ай бұрын

    YOU JUST SAVE MY LIFE

  • @WrathofMath

    @WrathofMath

    10 ай бұрын

    Awesome! Thanks for watching!

  • @hcphcp7114
    @hcphcp71143 күн бұрын

    thank you so much

  • @WrathofMath

    @WrathofMath

    Күн бұрын

    Glad to help - thanks for watching!

  • @insanevehicles4471
    @insanevehicles44716 ай бұрын

    thank you so so so so so soooooooooooo.....much

  • @raalfize7977
    @raalfize79772 жыл бұрын

    Man ! Thanks

  • @WrathofMath

    @WrathofMath

    2 жыл бұрын

    My pleasure, thanks for watching and let me know if you ever have any graph theory video requests!

  • @tylermoneysniper5070
    @tylermoneysniper5070 Жыл бұрын

    very good

  • @WrathofMath

    @WrathofMath

    Жыл бұрын

    Thank you!

  • @AntiJew964
    @AntiJew9646 ай бұрын

    thanks bro

  • @WrathofMath

    @WrathofMath

    6 ай бұрын

    Glad to help!

  • @Fine_Mouche
    @Fine_Mouche Жыл бұрын

    And what make a graph uniquely (1 way to 2 colore it) or not( 1+ ways to colore it) 2-colored ?

  • @kkch980
    @kkch9805 ай бұрын

    Very good explanation, thanks, Btw now is 03.05, will have a test at 10.00am, wish me luck

  • @WrathofMath

    @WrathofMath

    5 ай бұрын

    Best of luck!

  • @theroyaltyfamilyfanpage9542
    @theroyaltyfamilyfanpage95422 жыл бұрын

    Great video, Can you please do a video on combined random variables I have a question if V~ Geom(p) with p = 0.67 and that W = 2V to Find P(W>=6) how do I approach such question! Mery Christmas btw

  • @nuche3931

    @nuche3931

    2 жыл бұрын

    That's a very interesting question,

  • @theroyaltyfamilyfanpage9542

    @theroyaltyfamilyfanpage9542

    2 жыл бұрын

    @@nuche3931 I still cant figure out a way around it

  • @nuche3931

    @nuche3931

    2 жыл бұрын

    @@theroyaltyfamilyfanpage9542 would finding p(w>=3) work

  • @marios_papadakis_
    @marios_papadakis_ Жыл бұрын

    Bro you saved me!

  • @WrathofMath

    @WrathofMath

    Жыл бұрын

    Glad to help - thanks for watching!

  • @krasimirronkov17
    @krasimirronkov172 жыл бұрын

    Is the number theory video coming

  • @notawesomebread
    @notawesomebread10 ай бұрын

    liked immediately when i saw the christmas getup

  • @WrathofMath

    @WrathofMath

    10 ай бұрын

    Haha thank you! I know it's distracting to some viewers but I get a real kick out of it.

  • @_orkun_
    @_orkun_5 ай бұрын

    Thanks. Your consciousness is eternal. You leave your body with your energetic bodies (mind is one of them), and you still exist after death.

  • @Fine_Mouche
    @Fine_Mouche Жыл бұрын

    If I don't talk nonsense, the 4 colors theorem say there are no 5-colorable graph, no ? (in the sens 4 colors could be used)

  • @musabsarjo
    @musabsarjo5 ай бұрын

    I understand it like If vertices number is odd is bipartite if it is even it is not bipartite sorry for bad English if any mistakes

  • @musabsarjo

    @musabsarjo

    5 ай бұрын

    So i discovered that i am wrong 😂😂

  • @achrafBadiry
    @achrafBadiry Жыл бұрын

    But how can we prove that a given graph has no odd cycles ?

  • @hangyihao8732
    @hangyihao8732 Жыл бұрын

    I think that is a little bit similar to "four color theorem"🤔

  • @manofsteel6173
    @manofsteel6173 Жыл бұрын

    This guy is perfect in 1.25x

  • @kanishkgoyal6716
    @kanishkgoyal67162 ай бұрын

    man looks like timothee chalamet if he was a cs student

  • @seirayn3909
    @seirayn3909Ай бұрын

    THAKSKSKSKSKSKS