Problem
COM-B2-M07-P011 Colouring by Distance
Let a connected graph contain no odd cycles. Choose a vertex \(v\). Prove that colouring vertices by the parity of their distance from \(v\) gives a bipartition.
If an edge joins vertices with the same distance parity, obtain an odd cycle.
Colour vertices at even distance from \(v\) into one part and vertices at odd distance into the other. We need to prove that no edge joins vertices in the same part.
Suppose an edge \(xy\) joins two vertices with the same distance parity. Take shortest paths from \(v\) to \(x\) and from \(v\) to \(y\). These paths have a common initial segment; after removing it, the remaining two paths have total even length. Adding edge \(xy\) gives an odd cycle. This is forbidden. Hence every edge joins different parts.
Suitable after discussing BFS layers.