Graphs

Graph Patterns: Bipartite Graph Verification

May 2026

7 min read

If a problem asks whether a group of people can be divided into two teams where no enemies are on the same team, you are being asked to check if the graph is Bipartite.

Introduction

A Bipartite Graph is a graph whose vertices can be divided into two disjoint sets such that every edge connects a vertex in the first set to a vertex in the second set.

Mathematically, a graph is bipartite if and only if it does not contain a cycle of odd length.

The Graph Coloring Approach

The standard way to solve this is through "Graph Coloring."

We attempt to color the graph using only two colors (represented as 0 and 1). We start at a node, paint it color 0, and then mandate that all of its direct neighbors must be painted color 1.

As we traverse the graph, if we ever encounter a neighbor that is already painted, we check its color. If the neighbor has the exact same color as the current node, the bipartite rule is broken.

Implementation

java

class Solution {
    public boolean isBipartite(int V, ArrayList<ArrayList<Integer>> adj) {
        int[] color = new int[V];
        Arrays.fill(color, -1);
        
        // Handle disconnected components
        for (int i = 0; i < V; i++) {
            if (color[i] == -1) {
                if (!checkBipartiteBFS(i, adj, color)) return false;
            }
        }
        return true;
    }

    private boolean checkBipartiteBFS(int start, ArrayList<ArrayList<Integer>> adj, int[] color) {
        Queue<Integer> q = new LinkedList<>();
        q.add(start);
        color[start] = 0; // Paint the first node color 0
        
        while (!q.isEmpty()) {
            int node = q.poll();
            
            for (int neighbor : adj.get(node)) {
                // If the neighbor is unpainted, paint it the OPPOSITE color
                if (color[neighbor] == -1) {
                    color[neighbor] = 1 - color[node];
                    q.add(neighbor);
                } 
                // If the neighbor has the SAME color, it's not bipartite
                else if (color[neighbor] == color[node]) {
                    return false;
                }
            }
        }
        return true;
    }
}