Bipartite Graph

Given an undirected graph with V vertices (0 .. V-1) and an edge list edges, return true if it is bipartite — its vertices can be split into two groups so that every edge connects a vertex in one group to a vertex in the other — and false otherwise.

Hints

· Stuck? Reveal one nudge at a time.

Try to 2-colour the graph so no edge joins same-coloured vertices.

Colour each neighbour the opposite of the current vertex during BFS/DFS.

A same-coloured edge (equivalently, an odd cycle) means it isn't bipartite.

Common doubts

Colours alternate along any path, so a cycle returns to the start with a consistent colour only if its length is even; an odd cycle forces a conflict.

No — swapping all colours gives an equally valid 2-colouring, so start each component with either colour.

Either works and both are O(V+E); the colouring rule is identical.

Interview follow-ups

· What an interviewer asks next.

Return the vertices grouped by their final colour.

Matching (jobs to workers), scheduling with two shifts, and 2-SAT-style constraint checks.

Fun facts

LeetCode 785 — bipartiteness is the graph-colouring warm-up with just two colours.
Bipartite graphs are exactly the graphs with no odd cycle — a classic theorem of König.

Asked at

AmazonFacebookMicrosoft

Frequently Sometimes Occasionally

Example 1

Input: V = 4, edges = [[0,1],[1,2],[2,3],[3,0]]
Output: true
Colours A,B,A,B work — an even cycle is bipartite.

Example 2

Input: V = 3, edges = [[0,1],[1,2],[2,0]]
Output: false
A triangle is an odd cycle; no valid 2-colouring exists.

Constraints

- 1 <= V <= 10^5 - 0 <= edges.length <= 10^5 - no self-loops or duplicate edges

A graph is bipartite iff it can be 2-coloured with no edge joining same-coloured vertices. Traverse each component (BFS or DFS), colouring each newly-seen vertex the opposite of the one you came from. If you ever find an edge to an already-coloured vertex of the same colour, a proper 2-colouring is impossible — return false. Survive the whole graph and it's bipartite. O(V + E).

The deeper fact: bipartite ⟺ no odd-length cycle. An odd cycle forces two adjacent vertices to share a colour; even cycles and trees never do.

Prerequisites

Before you start

· Concepts used directly in the solution.

2-colouring. alternate colours along edges.

Odd cycle. the obstruction to bipartiteness.

Clarifying questions

Questions to ask first

· Signals seniority before you write a line of code.

Setup

“Disconnected graph?”

Colour every component independently.

“What makes it fail?”

An edge between two same-coloured vertices (equivalently, an odd cycle).

The ideal opening — say it like this

I 2-colour with BFS/DFS, giving each neighbour the opposite colour; a same-coloured edge means not bipartite.

Equivalently, the graph is bipartite exactly when it has no odd-length cycle.

Understand the problem

Worked example — V = 4, edges [[0,1],[1,2],[2,3],[3,0]] (a 4-cycle)

colour 0=A, 1=B, 2=A, 3=B; edge 3-0 joins B-A -> ok -> bipartite (even cycle)

Key observations

1Aha

Neighbours get opposite colours

Colour is forced by parity from the start vertex.

2Aha

Same-colour edge ⇒ not bipartite

The single failure condition.

3Aha

Bipartite ⟺ no odd cycle

Odd cycles are the only obstruction.

Brute force vs optimal

	BFS colouring	DFS colouring
Container	queue	recursion
Time	O(V+E)	O(V+E)
Idea	colour opposite of parent	colour opposite of parent

Both 2-colour and check for conflicts identically. Full code is in the Approaches selector below.

Summary

Key takeaway

2-colour each component, giving neighbours opposite colours; a same-coloured edge (an odd cycle) means not bipartite. O(V+E).

colour start; BFS/DFS colouring neighbours opposite
if edge joins same colours -> not bipartite