What is a Bipartite Graph?

A graph is bipartite if its vertices can be divided into two disjoint sets such that every edge connects a vertex in one set to one in the other.

How to check if a graph is Bipartite?

Use a BFS or DFS to "2-color" the graph. If you ever find two adjacent nodes with the same color, the graph is NOT bipartite.

No, any graph containing an odd-length cycle (like a triangle or pentagon) cannot be bipartite.

Learn how to determine if a graph can be bipartite using 2-Coloring (BFS/DFS). Essential for matching problems and cycle analysis.

Ready to start

Speed

Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.

Can you divide a group of people into two teams such that no two teammates are friends?

If you can, the network of friendships is a Bipartite Graph.

We solve this by trying to color the graph with just two colors (e.g., Red and Blue).

Bipartite Graph: A graph where vertices can be split into two sets, U and V, such that every edge connects a vertex in U to one in V.
2-Coloring: If we can color every node either Red or Blue such that no two connected nodes have the same color, the graph is bipartite.
Odd Cycle Property: A graph is bipartite if and only if it contains no odd cycles.

Algorithm (BFS 2-Coloring):

Initialize an array color with 0 (uncolored) for all nodes.
Iterate through all nodes. If uncolored, start BFS:
Color the start node 1 (Red).
For each neighbor:
- If uncolored: Color it with the opposite color (2 if current is 1, 1 if current is 2) and push to queue.
- If already colored with same color: Conflict found! Return false.
If traversal completes without conflict, return true.

Watch the visualization:

Red Node: Assigned to Set A.
Blue Node: Assigned to Set B.
Conflict (Dark Red): Found a neighbor with the same color. Graph is NOT bipartite.

Use Bipartite Check when:

Directed Graphs: The definition applies to undirected graphs (though similar concepts exist for directed acyclicity).

"Can we split into two groups?", "Is there an odd cycle?", "2-Coloring possible?".

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.