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 nodesare 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

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 Acyclic^{1} graphs are bipartite. A cyclic^{2} graph is bipartite iff all its cycles are of even length. Some common *examples* of a bipartite graph include star graphs^{3}, grid graphs^{4} and gear graphs^{5}.