Year-End Discount: 10% OFF 1-year and 20% OFF 2-year subscriptions!

Trusted answers to developer questions
Trusted Answers to Developer Questions

Related Tags


What is a bipartite graph?

Educative Answers Team

Tired of LeetCode? 😩

Learn the 24 patterns to solve any coding interview question without getting lost in a maze of LeetCode-style practice problems. Practice your skills in a hands-on, setup-free coding environment. 💪

A bipartite graph also called a bi-graph, is a set of graph vertices, i.e, points where multiple lines meet, decomposed into two disjoint sets, meaning they have no element in common, such that no two graph vertices within the same set are adjacent.

Adjacent nodes are any two nodes that are connected by an edge.

A bipartite graph is a special case of a k-partite graph with k = 2. The illustration below shows some bipartite graphs, with vertices in each graph colored based on the disjoint set they belong to

svg viewer
Each color is connected to a different color.

Bipartite graphs are equivalent to two-colorable graphs i.e., coloring of the vertices using two colors in such a way that vertices of the same color are never adjacent along an edge. All Acyclic1 graphs are bipartite. A cyclic2 graph is bipartite iff all its cycles are of even length. Some common examples of a bipartite graph include star graphs3, grid graphs4 and gear graphs5.