![[Trees are Bipartite 2025-05-03 03.27.54.excalidraw|100]] > [!NOTE] Lemma > (Simple, undirected) [[Trees (graph theory)|trees]] are [[Graph Colouring|2-colourable]] (bipartite). ###### Proof \[MA241\] Let $T$ be a tree. Choose some root $v_0$, and orient the edges of $T$ to point away from $v_0$. Then the unique path from a vertex $v$ to $v_0$ is given by following edges "upstream". We colour a vertex $v$ red if the distance from $v$ to $v_0$ is odd, and blue otherwise. If $v$ and $w$ are adjacent vertices, say without loss of generality that we have a directed edge $v \rightarrow w$. Then the unique path from $w$ to $v_0$ passes through $v$, and their lengths differ by 1 . Thus they have different colours, i.e. our $2$-colouring is valid. Thus $T$ is bipartite.