Past exam of the mathematics course of the University of Cambridge / 2015 / iii / Paper 38 / 4 / b / Solution

Run Breadth-first search separately in every component of the undirected graph. Give a starting vertex colour zero and each newly discovered neighbour the opposite colour. Reject if an edge joins two vertices with the same assigned colour; otherwise accept after all components have been explored.

If the algorithm accepts, its assignments constitute a graph colouring with two colours. If it rejects, the two search-tree paths and the conflicting edge contain an odd cycle, on which alternating two colours cannot close consistently. Equivalently, a valid graph colouring with two colours fixes the parity of every path from a component's root, so the detected conflict is impossible in a two-colourable graph. The Breadth-first search work is $O(|V|+|E|)$ with adjacency lists. ThereforeThis is also the two-colourability criterion for bipartite graphs.