What is a Bipartite Graph? How do you check for it?

Difficulty: 4/10

graph traversal, graph coloring, distributed validation

Bipartite Graph

A bipartite graph is a graph whose vertices can be divided into two disjoint sets such that every edge connects vertices from different sets. A standard way to test this is graph coloring with two colors using BFS or DFS. If an edge connects two vertices having the same color, the graph is not bipartite.

javascript

1
Use two colors.
2
Adjacent vertices must have different colors.
3
BFS or DFS can perform the coloring.
4
A graph is bipartite if and only if it contains no odd-length cycle.
5
Complexity: O(V+E).

Scenario Questions

0-2 years experience

2-5 years experience

1Our matchmaking service stores users and events as a graph. Suddenly a new feature that adds edges between users broke the assumption that the graph is bipartite. How would you debug and verify the graph's bipartiteness?

Follow-up Questions