Bipartite Check and Graph Coloring — 2-Coloring with BFS or DFS [LC 785, LC 886, Google, Meta]

Problem Statement#

Given an undirected graph with n vertices, determine if it is bipartite — that is, can the vertices be split into two disjoint sets A and B such that every edge connects a vertex in A with a vertex in B? Equivalently, can the graph be 2-colored such that no two adjacent vertices share a color?

Constraints:

• 1 <= n <= 10^5
• 0 <= m <= 10^5
• The graph may be disconnected; multiple components must each be checked.

Example 1:

Input:  graph = [[1,3],[0,2],[1,3],[0,2]]
Output: true
Explanation: Color {0, 2} red and {1, 3} blue. Every edge crosses colors.

Example 2 (odd cycle):

Input:  graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Explanation: 0 -- 1 -- 2 -- 0 forms a triangle (odd cycle), which cannot be 2-colored.

Why This Problem Matters#

Bipartite graphs appear everywhere: matching engineers to projects, students to courses, advertisers to slots, GPUs to jobs. Whenever an interview problem mentions "two groups," "matching," or "compatibility," check first if the underlying graph is bipartite — many otherwise-hard problems become polynomial-time on bipartite graphs (maximum matching is one famous example).

LeetCode 785 (Is Graph Bipartite?) and 886 (Possible Bipartition) are the entry-level FAANG problems that test your ability to 2-color a graph in linear time. Bipartite checking also serves as a stepping stone to more advanced techniques: maximum bipartite matching (Hopcroft-Karp), Konig's theorem, vertex covers, and the famous 2-SAT reduction.

In production systems, bipartite tests show up in auction matching at Google, content-creator-to-advertiser allocation at Meta, and shipper-to-driver matching at Uber. Recognising bipartiteness is the gateway to applying matching algorithms that solve real-world allocation problems efficiently.

The Core Insight#

A graph is bipartite if and only if it has no odd-length cycle. The 2-coloring algorithm constructs a proof of bipartiteness or a witness odd cycle in linear time.

BFS approach: Pick any unvisited vertex, color it 0. BFS-expand, alternating colors layer by layer. If you ever encounter an already-colored neighbour with the same color as the current vertex, the graph contains an odd cycle and is not bipartite. Otherwise, the BFS completes and produces a valid 2-coloring.

DFS approach: Color a starting vertex 0. Recurse: for each neighbour, if uncolored, color it the opposite color and recurse; if colored the same as the current vertex, return false. The recursion bottom-out gives a valid coloring.

Both approaches run in O(V + E) and require O(V) space. BFS is often easier to write iteratively (no recursion limit concerns); DFS gives shorter code.

For disconnected graphs, loop over every vertex and start a fresh BFS/DFS for each unvisited one. Each component is independently bipartite or not.

Visual Dry Run#

graph = [[1,2,3],[0,2],[0,1,3],[0,2]]. Start BFS from vertex 0.

The triangle 0-1-2-0 is detected when 1's neighbour 2 already shares 1's color.

Solution (Optimal)#

Python#

from collections import deque
 
def is_bipartite_bfs(graph):
    n = len(graph)
    color = [-1] * n  # -1 means uncolored
    for start in range(n):
        if color[start] != -1:
            continue  # already explored
        color[start] = 0
        queue = deque([start])
        while queue:
            u = queue.popleft()
            for v in graph[u]:
                if color[v] == -1:
                    color[v] = 1 - color[u]  # flip color
                    queue.append(v)
                elif color[v] == color[u]:
                    return False  # odd cycle witnessed
    return True
 
def is_bipartite_dfs(graph):
    n = len(graph)
    color = [-1] * n
 
    def dfs(u, c):
        color[u] = c
        for v in graph[u]:
            if color[v] == -1:
                if not dfs(v, 1 - c):
                    return False
            elif color[v] == c:
                return False
        return True
 
    for i in range(n):
        if color[i] == -1 and not dfs(i, 0):
            return False
    return True

JavaScript#

function isBipartite(graph) {
    const n = graph.length;
    const color = new Array(n).fill(-1);
 
    for (let start = 0; start < n; start++) {
        if (color[start] !== -1) continue;
        color[start] = 0;
        const queue = [start];
        let head = 0;
        while (head < queue.length) {
            const u = queue[head++];
            for (const v of graph[u]) {
                if (color[v] === -1) {
                    color[v] = 1 - color[u];
                    queue.push(v);
                } else if (color[v] === color[u]) {
                    return false;
                }
            }
        }
    }
    return true;
}
 
function possibleBipartition(n, dislikes) {
    // LC 886: convert to graph and run isBipartite. People are 1-indexed.
    const graph = Array.from({ length: n + 1 }, () => []);
    for (const [a, b] of dislikes) { graph[a].push(b); graph[b].push(a); }
    const color = new Array(n + 1).fill(-1);
 
    function dfs(u, c) {
        color[u] = c;
        for (const v of graph[u]) {
            if (color[v] === -1) {
                if (!dfs(v, 1 - c)) return false;
            } else if (color[v] === c) {
                return false;
            }
        }
        return true;
    }
 
    for (let i = 1; i <= n; i++) {
        if (color[i] === -1 && !dfs(i, 0)) return false;
    }
    return true;
}

Complexity: Time O(V + E). Space O(V) for the color array plus O(V) for queue or recursion stack.

Common Mistakes#

1. Not handling disconnected graphs. A single BFS may not visit every vertex. Loop over all vertices and start fresh when uncolored.
2. Mixing color values. Use 0 and 1 (or 1 and 2). Avoid 0 vs null because null interferes with the "uncolored" sentinel.
3. Returning early on the first colored neighbour without a same-color check. Only conflict cases should fail.
4. Confusing directed and undirected graphs. Bipartiteness is defined for undirected graphs. Directed bipartiteness needs different definitions.
5. Off-by-one in 1-indexed problems. LC 886 uses 1-indexed people; allocate n + 1 slots.
6. Recursion depth on large graphs. Use iterative BFS or raise the recursion limit for n near 10^5.

Interview Tips#

• Open by stating the equivalence: "A graph is bipartite iff it has no odd cycle." This shows theoretical understanding.
• Mention both BFS and DFS implementations; offer the one the interviewer prefers.
• For disconnected graphs, explicitly mention the outer loop.
• For LC 886, walk through the reduction: dislikes become edges; the question is whether the dislike graph is bipartite.
• If asked about k-coloring (k > 2), state honestly that this is NP-complete in general but admits known polynomial-time algorithms for special graph classes (planar, bipartite).

Follow-up Questions#

1. Maximum bipartite matching: Use Hopcroft-Karp algorithm in O(E * sqrt(V)).
2. Konig's theorem: In bipartite graphs, max matching equals min vertex cover.
3. 2-SAT solver: Build implication graph, run Tarjan SCC, ensure variable and its negation lie in different SCCs.
4. What if the graph has self-loops? A self-loop is a 1-cycle (odd). The graph is automatically not bipartite.
5. LC 886 (Possible Bipartition): Direct application — bipartite check on the dislike graph.

Key Takeaways#

• A graph is bipartite if and only if it contains no odd-length cycle.
• BFS and DFS both 2-color the graph in O(V + E) time.
• For disconnected graphs, run the algorithm separately for each component.
• A conflict (same-color neighbour) witnesses an odd cycle and proves non-bipartiteness.
• Bipartite graphs unlock polynomial-time matching, vertex cover, and 2-SAT algorithms.
• LeetCode 785 and 886 are the standard FAANG interview problems that test the bipartite-check pattern in a single linear pass.