BFS works naturally for bipartite detection. Start from a node, color it . BFS explores in levels: all neighbors (level ), then neighbors of neighbors (level ), and so on. Nodes at even levels get color . Nodes at odd levels get color . This matches BFS's natural behavior perfectly. When you visit a neighbor, check: is it uncolored?
Give it the opposite color. Already colored? Verify it has the opposite color. Same color means the graph is not bipartite.