Faangprep Logo
Log inStart free
Browse curriculum

Bipartite Graph

A bipartite graph is one whose vertices can be split into two groups with every edge running between them; 2-coloring with BFS or DFS tests whether a graph is bipartite. It is essential for matching problems and cycle analysis.

SEED SET A

Set A

A

Set B

Empty

 

A is uncoloured and unreached. Put it in set A and grow outwards.

Next

B touches A, so it must go in the opposite set — set B.

Intuition

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 (in the figure, blue for Set A and green for Set B).

Concept

  • 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 with one of two colours 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.

How it Works

Algorithm (BFS 2-Coloring):
  1. Initialize an array color with 0 (uncolored) for all nodes.
  2. Iterate through all nodes. If uncolored, start BFS:
  3. Color the start node 1.
  4. 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.
  5. If traversal completes without conflict, return true.

Step-by-Step Breakdown

Watch the visualization:

  • Blue node: Assigned to Set A, where the search starts.
  • Green node: Assigned to Set B.
  • Red nodes and edge: Two joined nodes landed in the same set. Graph is NOT bipartite.
  • Set A and Set B: The panels list the members of each set.

When to Use

Use Bipartite Check when:

  • Allocating resources into two independent sets.
  • Stable Marriage problem and other matching algorithms.
  • Detecting odd cycles in a graph.

When NOT to Use

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

How to Identify

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

Applying for software engineering roles? Free, no sign-up:

AI resume checker — match your resume to the job description
Previous

Connected Components

Next

Dijkstra's Algorithm

Frequently Asked Questions

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.

Is an Odd-Cycle graph Bipartite?

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