Bipartite Graph Check

Problem Given an undirected graph, determine whether it is bipartite: can the nodes be 2-colored so that no edge connects two nodes of the same color?

Input / Output

• Input: graph as adjacency list (possibly disconnected).
• Output: boolean.

Constraints

• Up to 10^5 nodes/edges; O(V + E) expected.

Example

• Edges {0-1, 1-2, 2-0} (odd cycle / triangle) → false; a square 0-1-2-3-0 → true.