Proof: Regular Bipartite Graph is Balanced | Graph Theory, Partite Sets

If G is an r-regular bipartite graph, r greater than 0, with partite sets U and W, then |U| = |W|, that is, the number of vertices in both partite sets is the same! Such a bipartite graph - one with partite sets of equal cardinalities - is called balanced. We will prove this result in today's graph theory lesson!

The proof is fairly straightforward, remember a regular graph is one whose vertices all have the same degree, so we could count all edges of G by adding the degrees of all vertices in the partite set U. We know we won't double count any edges by doing this because no edge is incident to two vertices of U since U is a partite set. Similarly, we know we aren't missing any edges in our count because every edge of a bipartite graph is incident with exactly one vertex in each partite set.

So, if G is r-regular then the number of edges in G is r*|U|. However, by the same logic, we can count the edges by adding the degrees of vertices in W, so r*|U| = r*|W| and thus |U| = |W|.

Lesson on regular graphs:    • What are Regular Graphs? | Graph Theory  
Lesson on bipartite graphs:    • What is a Bipartite Graph? | Graph Th...  

I hope you find this video helpful, and be sure to ask any questions down in the comments!

********************************************************************
The outro music is by a friend of mine named Molly Ponkevitch, who, upon my request, kindly gave me permission to use her music in my outros. I usually put my own music in the outros, but I love Molly's music, and wanted to share it with those of you watching. Please check out her wonderful music and other work, as she also does poetry and more.

Molly's YouTube:    / @mollyponkevitch1512  
Molly's Instagram: https://www.instagram.com/dyx_soma/?h...
Molly's Website: https://www.mollyponkevitch.com/
********************************************************************

+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