What is a Bipartite Graph? | Graph Theory

What is a bipartite graph? We go over it in today’s lesson! I find all of these different types of graphs very interesting, so I hope you will enjoy this lesson. A bipartite graph is any graph whose vertex set can be partitioned into two disjoint sets (called partite sets), such that all edges of the graph join a vertex from one partite set to a vertex in the other partite set.

To describe bipartite graphs in a visual way (but not really because I am typing the explanation), a graph is bipartite if you can draw it as two distinct rows of vertices, where every edge goes from one row to the other row. The video will do this description more justice.

Let’s define bipartite graphs again but with some specific names. Let G = ( V, E ) be a graph. Then G is bipartite if and only if there exist two disjoint sets, X and Y, such that V = X U Y, and every edge of G is of the form xy, where x is in X and y is in Y. That is, every edge joins a vertex from X to a vertex in Y.

Let’s give an example of a bipartite graph. Let G = ( V, E ) be a graph where V = {1, 2, 3, 4, 5} and E = {{1, 2}, {3, 5}, {4, 2}, {2, 3}}. Then, G is a bipartite graph and we can verify this by observing this partition of G’s vertex set. Let X = {1, 3, 4} and Y = {2, 5}. Then notice every edge of G joins a vertex from X to a vertex in Y. Also, X and Y are disjoint (they have no common elements), and their union is equal to V. Thus, G is a bipartite graph because there exists a partition of its vertex set, into two disjoint sets X and Y, such that every edge in G joins a vertex from X to a vertex in Y.

◉Textbooks I Like◉
Graph Theory: https://amzn.to/3JHQtZj
Real Analysis: https://amzn.to/3CMdgjI
Proofs and Set Theory: https://amzn.to/367VBXP (available for free online)
Statistics: https://amzn.to/3tsaEER
Abstract Algebra: https://amzn.to/3IjoZaO
Discrete Math: https://amzn.to/3qfhoUn
Number Theory: https://amzn.to/3JqpOQd

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

+WRATH OF MATH+

◆ Support Wrath of Math on Patreon:   / wrathofmathlessons  

Follow Wrath of Math on...
● Instagram:   / wrathofmathedu  
● Facebook:   / wrathofmath  
● Twitter:   / wrathofmathedu  

Music Channel:    / seanemusic