---
title: "Bipartite check (two-coloring)"
url: https://algopath.pro/patterns/bipartite
language: en
summary: "Colour any one node, then colour each of its neighbours in the other colour. A conflict proves the graph is not bipartite."
updated: 2026-08-24
---

# Bipartite check (two-coloring)

Colour any one node, then colour each of its neighbours in the other colour. A conflict proves the graph is not bipartite.

## How does Bipartite check (two-coloring) work?

Start with every node uncoloured. Then loop over all of them.

An uncoloured node begins a new walk. Paint it with the first colour.

Visit each neighbour in turn. Paint an uncoloured neighbour with the opposite colour.

A neighbour that already has a colour must differ from the current node. If they match, the graph fails.

A conflict means an odd cycle exists somewhere. No two-colouring can survive one of those.

Repeat for every component. The graph is bipartite only when all of them pass.

- `colour[0] = A` The graph is a triangle: 0-1, 1-2 and 2-0.
- `colour[1] = B` Its neighbour takes the other colour.
- `colour[2] = A` Node 2 sits next to node 1, so it takes A.
- `edge 2-0: A against A` Both ends carry the same colour. The check fails.
- `answer = false` A triangle is an odd cycle. Two colours can never fit it.

## When should you use Bipartite check (two-coloring)?

- split into two groups with no conflict inside a group
- two-color the graph
- detect an odd-length cycle
- us vs them / two-shift scheduling / two-room assignment
- possible bipartition of conflict pairs

## What is Bipartite check (two-coloring) confused with?

- **Graph BFS / DFS** - The walk itself is identical. The only addition is a colour carried on each node.
- **Connected components** - Both loop over unvisited nodes and start a walk. Here a walk can also fail.
- **Union-find (disjoint set)** - A weighted disjoint set answers the same question. It suits edges that arrive over time.
- **Backtracking** - Three or more colours needs a search with undo. Two colours never needs a choice.

## What is the time and space complexity of Bipartite check (two-coloring)?

V nodes and E edges give O(V + E). Each node is coloured once and each edge checked twice.

## A worked example of Bipartite check (two-coloring)

### Split people into two groups

You get a number of people and a list of pairs who dislike each other.

Split everyone into two groups so that nobody shares a group with someone they dislike.

Each person is a node and each dislike is an edge.

Run the two-colouring over every component. A single conflict makes the split impossible.

```javascript
function possibleBipartition(n, dislikes) {
    const graph = Array.from({ length: n + 1 }, () => []);
    for (const [a, b] of dislikes) {
        graph[a].push(b);
        graph[b].push(a);
    }

    const colour = new Array(n + 1).fill(0);

    for (let start = 1; start <= n; start++) {
        if (colour[start] !== 0) continue; // already placed by an earlier walk

        colour[start] = 1;
        const queue = [start];

        for (let i = 0; i < queue.length; i++) {
            const node = queue[i];

            for (const next of graph[node]) {
                if (colour[next] === colour[node]) return false; // same side
                if (colour[next] === 0) {
                    colour[next] = -colour[node];
                    queue.push(next);
                }
            }
        }
    }

    return true;
}
```

## Common mistakes with Bipartite check (two-coloring)

- **Walking only from the first node** A disconnected graph can hide the conflict elsewhere. Start a walk from every uncoloured node.
- **Storing only a visited flag** You need the colour, not just whether it was seen. One array can carry both.
- **Colouring on removal from the queue** The same node can then enter twice with different colours. Colour it as you push it.
- **Expecting failure to look specific** The only possible cause is an odd cycle. A graph with only even cycles always passes.

## Which interview problems use Bipartite check (two-coloring)?

- **Is graph bipartite** The plain form, over an adjacency list.
- **Possible bipartition** Dislike pairs become the edges.
- **Divide players into two teams** The same two-colouring, worded differently.
- **Detect an odd cycle** The same test, asked the other way round.
- **Maximum bipartite matching** Only meaningful once the two sides are known.
- **Flower planting with no adjacent same** Four colours, so a greedy pass is enough.
- **Graph colouring with three colours** Backtracking, since two colours no longer decide it.

## JavaScript

```javascript
function isBipartite(n, adj) {
    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];
        while (queue.length) {
            const node = queue.shift();
            for (const next of adj[node] || []) {
                if (color[next] === -1) {
                    color[next] = 1 - color[node];
                    queue.push(next);
                } else if (color[next] === color[node]) {
                    return false; // same color on both ends: odd cycle
                }
            }
        }
    }
    return true;
}
```

## Python

```python
from collections import deque

def is_bipartite(n, adj):
    color = [-1] * n
    for start in range(n):
        if color[start] != -1:
            continue
        color[start] = 0
        queue = deque([start])
        while queue:
            node = queue.popleft()
            for nxt in adj.get(node, []):
                if color[nxt] == -1:
                    color[nxt] = 1 - color[node]
                    queue.append(nxt)
                elif color[nxt] == color[node]:
                    return False  # same color on both ends: odd cycle
    return True
```

## PHP

```php
function isBipartite(int $n, array $adj): bool {
    $color = array_fill(0, $n, -1);
    for ($start = 0; $start < $n; $start++) {
        if ($color[$start] !== -1) continue;
        $color[$start] = 0;
        $queue = [$start];
        while ($queue) {
            $node = array_shift($queue);
            foreach ($adj[$node] ?? [] as $next) {
                if ($color[$next] === -1) {
                    $color[$next] = 1 - $color[$node];
                    $queue[] = $next;
                } elseif ($color[$next] === $color[$node]) {
                    return false; // same color on both ends: odd cycle
                }
            }
        }
    }
    return true;
}
```