Domain 2MediumMEDIUM

Is Graph Bipartite?

Determine if an undirected graph is bipartite by attempting to color it with two colors using DFS, ensuring no adjacent nodes share the same color.

Domain: medium•Updated: 2026-08-31
#DFS#Adjacency List#O(V + E)#O(V)

Problem Breakdown

We are given an undirected graph represented as an adjacency list (graph). The goal is to determine if this graph can be partitioned into two independent sets (A and B) such that every edge connects a node in A to one in B. This is equivalent to checking if the graph is 2-colorable.

Inputs:

  • graph: List of lists, where graph[u] contains neighbors of u.
  • Implicit: Number of nodes n = len(graph), indexed 0 to n-1.

Outputs:

  • Boolean (True if bipartite, False otherwise).

Implicit Constraints & Edge Cases:

  • Disconnected Graphs: The graph might not be connected (multiple components). We must ensure every component is checked for validity; a single invalid cycle in one disconnected part makes the whole result False.
  • Single Node/Empty Edges: A node with no edges is trivially bipartite.
  • Conflict Detection: If we encounter an edge between two nodes already colored, they must have different colors. Same color = not bipartite.

Intuition

A brute-force approach would try to assign every possible combination of partitions (2^n possibilities), which is exponential and infeasible for larger graphs (O(2N)O(2^N)).

The key insight is that this problem maps directly to a graph coloring task using two colors (e.g., 0 and 1). If we traverse the graph, assigning alternating colors as we go:

  1. Start at an unvisited node, assign it Color A.
  2. All its neighbors must be assigned Color B.
  3. Their neighbors must be back to Color A.

If during this traversal we encounter a neighbor that is already colored with the same color as our current node, we have found an odd-length cycle, which violates bipartiteness. Since the graph can be disconnected, we need to repeat this process for every unvisited node until all components are processed.

Approach

  1. Initialize a colors array of size n, filled with -1 (representing unvisited).
  2. Iterate through each node from 0 to n-1. This loop handles disconnected components naturally.
  3. If the current node is unvisited (-1):
    • Start a traversal (DFS) starting at this node.
    • Assign it an initial color (e.g., 0).
  4. During traversal:
    • For each neighbor of the current node:
      • If unvisited, assign the opposite color and continue traversal.
      • If visited, check if its color matches the current node’s color.
  5. Return False immediately upon finding a conflict (same colors on adjacent nodes).
  6. If we finish traversing all components without conflicts, return True.

Complexity Analysis

  • Time Complexity: O(V+E)O(V + E), where VV is the number of nodes and EE is the total number of edges. We visit every node once via the outer loop or traversal start, and inspect every edge exactly twice (once from each end) during neighbor checks in an undirected graph.
  • Space Complexity: O(V)O(V) for the colors array to store state. Additionally, we use O(V)O(V) space for the recursion stack (DFS) or queue (BFS), which is bounded by the number of nodes.

Solution

def isBipartite(graph):
    n = len(graph)
    # -1 represents unvisited; 0 and 1 represent the two sets/colors
    colors = [-1] * n
    
    for i in range(n):
        if colors[i] == -1:
            # Start traversal (DFS) from this node to handle disconnected components
            stack = [i]
            colors[i] = 0
            
            while stack:
                curr_node = stack.pop()
                
                for neighbor in graph[curr_node]:
                    if colors[neighbor] == -1:
                        # Assign opposite color and push to stack
                        colors[neighbor] = 1 - colors[curr_node]
                        stack.append(neighbor)
                    elif colors[neighbor] == colors[curr_node]:
                        # Conflict found: adjacent nodes share the same set/color
                        return False
                        
    return True

Edge Cases Handled

  • Disconnected Components: The outer loop for i in range(n) ensures we start a traversal for every unvisited node, covering isolated parts of the graph.
  • Single Node Graphs: If n=1, the inner loop runs once with no neighbors; returns True correctly as it is bipartite by definition (no edges to violate partition).
  • Immediate Conflict Detection: The check inside the neighbor iteration ensures we return False instantly upon finding an odd cycle, rather than continuing unnecessarily.