> [!NOTE] Lemma > A (simple, undirected) [[Graphs|graph]] is [[Graph Colouring|2-colourable]] if and only if it contains no odd-length cycles. ###### Proof For the non-trivial direction, use the 2-colouring of the spanning tree.