Use BFS (or DFS) to try coloring the graph with colors. Start at any uncolored node, assign color . For each neighbor, assign the opposite color. If a neighbor already has a color and it matches the current node's color, the graph is not bipartite.
The graph might be disconnected, so repeat the process for every uncolored node. A graph is bipartite if and only if it contains no odd-length cycles. The BFS coloring approach detects exactly this condition.