Bipartite Graphs and Two-Coloring: A Coding Interview Pattern You Can Learn in an Afternoon

"Is this graph bipartite?" shows up in coding interviews more often than people expect, sometimes directly and sometimes disguised as "can these people be split into two groups with no enemies in the same group?" The underlying technique, two-coloring with BFS or DFS, is short, elegant, and easy to get right once you see it. What bipartite means A graph is bipartite if you can split its vertices into two sets so that every edge connects a vertex in one set to a vertex in the other. Equivalently, you can color every vertex red or blue so that no edge joins two vertices of the same color. A classic theorem tells you why this matters: a graph is bipartite exactly when it has no odd-length cycle. The BFS approach Pick any uncolored vertex, color it 0, and BFS outward. Each neighbor gets the opposite color. If you ever find a neighbor already colored the same as the current vertex, the graph is not bipartite. from collections import deque def is_bipartite(graph): n = len(graph) color = [-1] * n for start in range(n): if color[start] != -1: continue color[start] = 0 q = deque([start]) while q: u = q.popleft() for v in graph[u]: if color[v] == -1: color[v] = 1 - color[u] q.append(v) elif color[v] == color[u]: return False return True Note the outer loop: graphs in interviews are often disconnected, and forgetting to start a BFS from every uncolored vertex is the most common bug. Complexity: O(V + E) time and O(V) space. Disguised versions 1. Possible Bipartition: people with "dislike" pairs must be split into two groups. Build a graph from the dislike pairs and run the same check. 2. Team assignment or seating problems: any "two groups, conflicts must be separated" statement is a bipartite check. 3. Grid problems: a chessboard coloring is a bipartite structure, which helps with domino tiling arguments. 4. Matching problems: assigning workers to jobs is maximum bipartite matching. In interviews you are usually asked to recognize it rather than implement Hopcroft-Karp, but knowing the name helps. Union-find alternative You can also check bipartiteness with union-find: for each vertex u, union all its neighbors together, and check that u is never in the same set as a neighbor. It is a nice talking point if the interviewer asks for another approach. Follow-up questions - Return the two groups, not just true or false: return the color array. - What about three colors? Three-coloring is NP-complete, so expect a discussion about backtracking and why there is no efficient general solution. - What if edges arrive one at a time? Use union-find with parity to maintain the answer incrementally. How to explain it Start with the definition in plain words, connect it to "no odd cycles", then describe the coloring process before writing code. Mention disconnected components explicitly; interviewers often watch for that. Under pressure, small details like the outer loop slip away. Linkjob AI (https://linkjob.ai) offers real-time help during job interviews and technical interviews, helping you keep your reasoning structured while you code and talk. It works best as support for skills you have practiced. Takeaway: when a problem says "split into two groups with constraints between pairs", reach for two-coloring.