A graph is bipartite if you can split its nodes into two groups such that every edge goes between the groups — never within one. Equivalently, you can colour every node with one of two colours so that no edge joins two same-coloured nodes. The two phrasings are the same idea, so "bipartite" and "2-colourable" are interchangeable.
Think of two teams: an edge means "these two can't be on the same team." A graph is bipartite exactly when such a split is possible.
Walk the graph (BFS or DFS). Colour the start node A; colour every neighbour the opposite colour B; their neighbours back to A; and so on, alternating at each step:
color = {} // 0 = uncoloured, 1 = A, -1 = B
for each start in nodes:
if color[start] != 0: continue
color[start] = 1
queue = [start]
while queue is not empty:
cur = queue.removeFirst()
for each nb in graph[cur]:
if color[nb] == 0:
color[nb] = -color[cur] // opposite colour
queue.append(nb)
else if color[nb] == color[cur]:
return false // same-coloured edge -> not bipartite
return true
If you ever reach a neighbour that's already coloured the same as the current node, the alternation has clashed — the graph is not bipartite. Run this from every uncoloured node so disconnected components are all checked.
There's a neat characterisation: a graph is bipartite if and only if it has no odd-length cycle. Colours must flip on every edge, so going around a cycle returns to the start with the colour flipped an even number of times only when the cycle is even. A triangle (length 3) forces a node to clash with itself — impossible to 2-colour.
The whole walk is O(V + E). The next problem, Can Color, is exactly this test.