Is Graph Bipartite

Check if a graph can be colored with exactly two colors such that no two adjacent nodes have the same color

Language Selection

Choose your preferred programming language

Showing: Python

Is Graph Bipartite

Problem Statement

A graph is bipartite if the nodes can be partitioned into two independent sets A and B such that every edge in the graph connects a node in set A and a node in set B.

Given an undirected graph, return true if and only if it is bipartite.

Input/Output Specifications

Input: graph - an adjacency list where graph[u] is a list of nodes that node u is adjacent to
Output: A boolean indicating whether the graph is bipartite
Constraints:
- graph.length == n
- 1 <= n <= 100
- 0 <= graph[u].length < n
- 0 <= graph[u][i] <= n - 1
- graph[u] does not contain u
- All values of graph[u] are unique
- If graph[u] contains v, then graph[v] contains u (undirected graph)

Examples

Example 1:

Input: graph = [[1,2,3],[0,2],[0,1,3],[0,2]]
Output: false
Explanation: 
There is no way to partition the nodes into two independent sets such that every edge connects a node in one and a node in the other.

Example 2:

Input: graph = [[1,3],[0,2],[1,3],[0,2]]
Output: true
Explanation: 
We can partition the nodes into two sets: {0, 2} and {1, 3}.
Every edge connects a node from one set to a node from the other set.

Example 3:

Input: graph = [[1],[0,3],[3],[1,2]]
Output: true
Explanation:
Nodes can be partitioned as: {0, 3} and {1, 2}.

Example 4:

Input: graph = [[]]
Output: true
Explanation:
Single node with no edges is bipartite.

Solution Approaches

Approach 1: DFS Graph Coloring (Optimal)

Use depth-first search to color the graph with two colors and check for conflicts.

Algorithm Explanation

Two-Coloring: Attempt to color each node with one of two colors (0 or 1)
DFS Traversal: For each unvisited node:
- Assign it color 0
- Recursively color all neighbors with the opposite color
- If any neighbor already has the same color, return false
Disconnected Components: Handle multiple connected components
Result: Graph is bipartite if all nodes can be colored without conflicts

Implementation

Python:

class Solution:
    """
    DFS graph coloring approach for bipartite check
    Time: O(V + E) where V is vertices, E is edges
    Space: O(V) for color array and recursion stack
    """
    
    def isBipartite(self, graph: list[list[int]]) -> bool:
        n = len(graph)
        color = [-1] * n  # -1: uncolored, 0: color A, 1: color B
        
        def dfs(node, c):
            color[node] = c
            
            for neighbor in graph[node]:
                if color[neighbor] == c:  # Same color conflict
                    return False
                if color[neighbor] == -1 and not dfs(neighbor, 1 - c):
                    return False
            
            return True
        
        # Check all connected components
        for i in range(n):
            if color[i] == -1:
                if not dfs(i, 0):
                    return False
        
        return True

Java:

class Solution {
    /**
     * DFS graph coloring approach for bipartite check
     * Time: O(V + E) where V is vertices, E is edges
     * Space: O(V) for color array and recursion stack
     */
    
    private int[][] graph;
    private int[] color;
    
    public boolean isBipartite(int[][] graph) {
        this.graph = graph;
        int n = graph.length;
        color = new int[n];
        Arrays.fill(color, -1); // -1: uncolored, 0: color A, 1: color B
        
        // Check all connected components
        for (int i = 0; i < n; i++) {
            if (color[i] == -1) {
                if (!dfs(i, 0)) {
                    return false;
                }
            }
        }
        
        return true;
    }
    
    private boolean dfs(int node, int c) {
        color[node] = c;
        
        for (int neighbor : graph[node]) {
            if (color[neighbor] == c) { // Same color conflict
                return false;
            }
            if (color[neighbor] == -1 && !dfs(neighbor, 1 - c)) {
                return false;
            }
        }
        
        return true;
    }
}

Go:

// isBipartite - DFS graph coloring approach for bipartite check
// Time: O(V + E) where V is vertices, E is edges
// Space: O(V) for color array and recursion stack
func isBipartite(graph [][]int) bool {
    n := len(graph)
    color := make([]int, n)
    for i := range color {
        color[i] = -1 // -1: uncolored, 0: color A, 1: color B
    }
    
    var dfs func(int, int) bool
    dfs = func(node, c int) bool {
        color[node] = c
        
        for _, neighbor := range graph[node] {
            if color[neighbor] == c { // Same color conflict
                return false
            }
            if color[neighbor] == -1 && !dfs(neighbor, 1-c) {
                return false
            }
        }
        
        return true
    }
    
    // Check all connected components
    for i := 0; i < n; i++ {
        if color[i] == -1 {
            if !dfs(i, 0) {
                return false
            }
        }
    }
    
    return true
}

JavaScript:

/**
 * DFS graph coloring approach for bipartite check
 * Time: O(V + E) where V is vertices, E is edges
 * Space: O(V) for color array and recursion stack
 */
function isBipartite(graph) {
    const n = graph.length;
    const color = new Array(n).fill(-1); // -1: uncolored, 0: color A, 1: color B
    
    function dfs(node, c) {
        color[node] = c;
        
        for (const neighbor of graph[node]) {
            if (color[neighbor] === c) { // Same color conflict
                return false;
            }
            if (color[neighbor] === -1 && !dfs(neighbor, 1 - c)) {
                return false;
            }
        }
        
        return true;
    }
    
    // Check all connected components
    for (let i = 0; i < n; i++) {
        if (color[i] === -1) {
            if (!dfs(i, 0)) {
                return false;
            }
        }
    }
    
    return true;
}

C#:

public class Solution {
    /// <summary>
    /// DFS graph coloring approach for bipartite check
    /// Time: O(V + E) where V is vertices, E is edges
    /// Space: O(V) for color array and recursion stack
    /// </summary>
    
    private int[][] graph;
    private int[] color;
    
    public bool IsBipartite(int[][] graph) {
        this.graph = graph;
        int n = graph.Length;
        color = new int[n];
        Array.Fill(color, -1); // -1: uncolored, 0: color A, 1: color B
        
        // Check all connected components
        for (int i = 0; i < n; i++) {
            if (color[i] == -1) {
                if (!Dfs(i, 0)) {
                    return false;
                }
            }
        }
        
        return true;
    }
    
    private bool Dfs(int node, int c) {
        color[node] = c;
        
        foreach (int neighbor in graph[node]) {
            if (color[neighbor] == c) { // Same color conflict
                return false;
            }
            if (color[neighbor] == -1 && !Dfs(neighbor, 1 - c)) {
                return false;
            }
        }
        
        return true;
    }
}

Approach 2: BFS Graph Coloring

Use breadth-first search to color the graph level by level.

Algorithm Explanation

Level-by-Level Coloring: Use BFS to color nodes level by level
Queue Processing: For each unvisited node:
- Start BFS with color 0
- Color all neighbors with opposite color
- Check for color conflicts
Component Handling: Process all disconnected components
Validation: Return false if any color conflict is detected

Implementation

Python:

from collections import deque

class Solution:
    """
    BFS graph coloring approach for bipartite check
    Time: O(V + E) where V is vertices, E is edges
    Space: O(V) for color array and queue
    """
    
    def isBipartite(self, graph: list[list[int]]) -> bool:
        n = len(graph)
        color = [-1] * n  # -1: uncolored, 0: color A, 1: color B
        
        for start in range(n):
            if color[start] == -1:
                # Start BFS for this component
                queue = deque([start])
                color[start] = 0
                
                while queue:
                    node = queue.popleft()
                    
                    for neighbor in graph[node]:
                        if color[neighbor] == color[node]:  # Conflict
                            return False
                        if color[neighbor] == -1:
                            color[neighbor] = 1 - color[node]
                            queue.append(neighbor)
        
        return True

Java:

class Solution {
    /**
     * BFS graph coloring approach for bipartite check
     * Time: O(V + E) where V is vertices, E is edges
     * Space: O(V) for color array and queue
     */
    
    public boolean isBipartite(int[][] graph) {
        int n = graph.length;
        int[] color = new int[n];
        Arrays.fill(color, -1); // -1: uncolored, 0: color A, 1: color B
        
        for (int start = 0; start < n; start++) {
            if (color[start] == -1) {
                // Start BFS for this component
                Queue<Integer> queue = new LinkedList<>();
                queue.offer(start);
                color[start] = 0;
                
                while (!queue.isEmpty()) {
                    int node = queue.poll();
                    
                    for (int neighbor : graph[node]) {
                        if (color[neighbor] == color[node]) { // Conflict
                            return false;
                        }
                        if (color[neighbor] == -1) {
                            color[neighbor] = 1 - color[node];
                            queue.offer(neighbor);
                        }
                    }
                }
            }
        }
        
        return true;
    }
}

Complexity Analysis

DFS Approach

Time Complexity: O(V + E) where V is number of vertices and E is number of edges
Space Complexity: O(V) for color array and O(V) for recursion stack = O(V)

BFS Approach

Time Complexity: O(V + E) where V is number of vertices and E is number of edges
Space Complexity: O(V) for color array and O(V) for queue = O(V)

Key Insights

Two-Coloring Problem: Bipartite check is equivalent to graph two-coloring
Odd Cycle Detection: A graph is bipartite if and only if it contains no odd-length cycles
Connected Components: Must check all disconnected components separately
Color Representation: Can use any two distinct values (0/1, true/false, etc.)

Edge Cases

Empty Graph: No nodes - considered bipartite
Single Node: One node with no edges - bipartite
Two Nodes Connected: Always bipartite
Triangle (3-cycle): Odd cycle - not bipartite
Square (4-cycle): Even cycle - bipartite
Disconnected Graph: Multiple components to check independently
Self-Loop: Not allowed per problem constraints (undirected graph)

Test Cases

# Test cases for validation
def test_bipartite():
    solution = Solution()
    
    # Test case 1: Simple bipartite (square)
    assert solution.isBipartite([[1,3],[0,2],[1,3],[0,2]]) == True
    
    # Test case 2: Triangle (odd cycle)
    assert solution.isBipartite([[1,2],[0,2],[0,1]]) == False
    
    # Test case 3: Single node
    assert solution.isBipartite([[]]) == True
    
    # Test case 4: Two nodes
    assert solution.isBipartite([[1],[0]]) == True
    
    # Test case 5: Complex non-bipartite
    assert solution.isBipartite([[1,2,3],[0,2],[0,1,3],[0,2]]) == False
    
    # Test case 6: Disconnected components
    assert solution.isBipartite([[1],[0],[3],[2]]) == True
    
    # Test case 7: Larger bipartite graph
    assert solution.isBipartite([[1,3],[0,2],[1,3],[0,2]]) == True

Follow-up Questions

Graph Coloring: Extend to k-coloring for any k colors
Maximum Bipartite Matching: Find maximum matching in bipartite graph
Minimum Vertex Cover: Find minimum vertex cover in bipartite graph
Bipartite Partition: Return the actual partition if graph is bipartite

Common Mistakes

Forgetting Disconnected Components: Not checking all components separately
Color Initialization: Using wrong initial color values or not initializing properly
Conflict Detection: Incorrect logic for detecting same-color conflicts
Edge Case Handling: Not handling single nodes or empty graphs correctly

Interview Tips

Understand Bipartite Definition: Clarify what makes a graph bipartite
Choose Approach: Both DFS and BFS work - pick based on preference
Explain Two-Coloring: Connect the problem to graph coloring concepts
Handle Components: Remember to check all disconnected components
Trace Through Example: Walk through coloring process step by step
Discuss Optimizations: Mention early termination when conflict is found

Mathematical Properties

Bipartite Characterization: A graph is bipartite ⟺ it contains no odd cycles
Tree Property: All trees are bipartite graphs
Complete Bipartite: K_{m,n} is the complete bipartite graph with parts of size m and n
Chromatic Number: Bipartite graphs have chromatic number ≤ 2

Real-World Applications

Matching Problems: Assignment of workers to tasks
Conflict Resolution: Scheduling without conflicts
Network Analysis: Identifying two distinct groups in social networks
Resource Allocation: Distributing resources between two categories