testing bipartiteness
A graph is bipartite if you can split its vertices into two camps so that every edge runs between the camps and never inside one — like seating guests at two tables so no two friends share a table, or a schedule where every task connects a worker to a job. The natural way to picture it is colouring: paint each vertex red or blue so that no edge ever joins two vertices of the same colour. Many real situations (matchings, conflict graphs, scheduling) are exactly the question 'can this be split into two sides?', and graph search answers it in one pass.
The test is a coloured traversal. Run BFS (or DFS) from each unvisited vertex; colour the start red, and colour every newly discovered vertex the opposite of the vertex you reached it from. If you ever find an edge whose two endpoints already carry the same colour, stop: the graph is not bipartite. If you finish with no such clash, it is. Why is this correct? In BFS, a same-colour edge must join two vertices on levels of the same parity, and tracing both up to their common ancestor in the BFS tree produces a cycle whose length is odd. So a failed colouring is not an accident of your colour choices — it is a genuine odd cycle, and a classic theorem says a graph is bipartite exactly when it has no odd cycle. That theorem is what upgrades 'I couldn't 2-colour it' into the certain 'it cannot be 2-coloured'.
This runs in O(n + m), the cost of a single traversal, and it both decides the question and, on success, hands you the actual two-sided split for free. It is the gateway to bipartite matching and many scheduling models. One caveat to keep straight: bipartite means no odd cycle, and even cycles are perfectly fine — a 4-cycle or 6-cycle is bipartite. Also, you must test every connected component (start the search from each uncoloured vertex), since a graph can be bipartite in one piece and have a clash in another.
A 4-cycle a-b-c-d-a: colour a red, b blue, c red, d blue; the edge d-a joins blue and red — no clash, so it is bipartite (sides {a,c} and {b,d}). A triangle a-b-c-a: a red, b blue, then c must differ from both b and a but a and c are joined and both would be red — clash, an odd cycle, not bipartite.
Even cycles 2-colour cleanly; an odd cycle forces a same-colour edge, and that is the precise obstruction.
Bipartite is exactly 'no odd cycle', not 'no cycle' — graphs with even cycles can still be bipartite. And you must scan every component; one bad component makes the whole graph non-bipartite.