How Do You Check if a Graph is Bipartite?
Learn the two-coloring BFS/DFS technique to check if a graph is bipartite, with complexity analysis and interview-ready code.
Expected Interview Answer
A graph is bipartite if its vertices can be split into two groups so that every edge connects a vertex in one group to a vertex in the other, and you check this with a two-coloring BFS or DFS that fails the instant an edge connects two same-colored vertices.
Starting from any unvisited vertex, assign it color 0 and traverse its neighbors, coloring each unvisited neighbor the opposite color of the current vertex. If a traversal ever reaches an already-colored neighbor that shares the current vertex's color, the graph contains an odd-length cycle and cannot be bipartite. Because the graph may be disconnected, every unvisited vertex must start its own coloring pass, and the whole graph is bipartite only if every component passes. The algorithm runs in O(V + E) time using an adjacency list, matching the cost of a single BFS or DFS traversal.
- O(V + E) time using standard BFS or DFS
- Detects odd-length cycles as a side effect
- Foundation for matching and scheduling problems
- Works on disconnected graphs with per-component checks
AI Mentor Explanation
A tournament wants two divisions such that every scheduled match is always between one team from Division A and one from Division B, never same-division. You assign the first team to Division A, then every opponent it plays gets pushed into Division B, and their opponents get pushed back into Division A, spreading outward like a wave. If you ever discover a team already assigned to Division A being scheduled against another Division A team, the fixture list cannot be split this way. This wave-coloring approach is exactly how a bipartite check colors a graph two colors in one traversal.
Step-by-Step Explanation
Step 1
Pick an unvisited vertex
Assign it color 0 and add it to a BFS queue or start a DFS from it.
Step 2
Color neighbors the opposite color
Every unvisited neighbor gets the opposite color of the current vertex, then gets queued or recursed into.
Step 3
Check already-colored neighbors
If a neighbor is already colored and matches the current vertex color, the graph is not bipartite.
Step 4
Repeat for every component
Restart coloring from any remaining unvisited vertex until all vertices are checked.
What Interviewer Expects
- Explain the two-coloring intuition and why a same-color edge means failure
- Handle disconnected graphs by restarting the check per component
- State the O(V + E) time complexity
- Connect bipartiteness to odd-cycle detection
Common Mistakes
- Only checking one connected component and ignoring the rest of the graph
- Forgetting to track colors and instead only tracking visited/unvisited
- Assuming bipartite means no cycles at all, rather than no odd-length cycles
- Not handling self-loops, which always make a graph non-bipartite
Best Answer (HR Friendly)
“Checking if a graph is bipartite means trying to split all the nodes into two groups so every connection goes between the groups, never within one. I do this by coloring nodes alternately as I traverse, and if I ever find a connection between two same-colored nodes, I know the split is impossible.”
Code Example
from collections import deque
def is_bipartite(graph):
color = {}
for source in graph:
if source in color:
continue
color[source] = 0
queue = deque([source])
while queue:
node = queue.popleft()
for neighbor in graph[node]:
if neighbor not in color:
color[neighbor] = 1 - color[node]
queue.append(neighbor)
elif color[neighbor] == color[node]:
return False
return TrueFollow-up Questions
- How would you find the actual two partitions once you confirm bipartiteness?
- How does bipartite checking relate to two-colorability in graph coloring theory?
- How would you use this check to detect an odd-length cycle specifically?
- How would you adapt the check to run with DFS instead of BFS?
MCQ Practice
1. A graph is bipartite if and only if it contains no cycles of what kind?
A graph is bipartite exactly when it has no odd-length cycles; even-length cycles are fine.
2. What is the time complexity of a bipartite check using BFS on an adjacency list?
Each vertex and edge is visited once during the coloring traversal, giving O(V + E).
3. What causes a bipartite check to correctly return false?
An edge connecting two same-colored vertices means the two-coloring failed, so the graph is not bipartite.
Flash Cards
What defines a bipartite graph? — Vertices split into two groups where every edge connects one group to the other.
What algorithmic technique checks bipartiteness? — Two-coloring via BFS or DFS, failing on a same-color edge.
What graph property is equivalent to bipartiteness? — The graph has no odd-length cycles.
How do you handle a disconnected graph when checking bipartiteness? — Restart the coloring traversal from every unvisited vertex.