= 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. Therefore
$$
\boxed{\text{two-colourability is in }\mathbf P.}
$$
This is also the <two-colourability criterion for bipartite graphs>.
Back to article page
