In einem Baum gibt es zwischen zwei beliebigen Knoten genau einen Pfad. Das kannst du nutzen, indem du irgendeinen Knoten \( v \) als Wurzel des Baume wählst (wir färben sie jetzt mal blau) und dann, je nachdem ob die Länge des Pfades von \( v \) nach \( u \) für irgendeinen Knoten \( u \) gerade bzw. ungerade ist, du \( u \) mit blau oder mit rot färbst. Wenn jetzt zwei Knoten \( x \) und \( y \) durch eine Kante verbunden sind, so können sie nicht die gleiche Farbe haben, da ja die Länge des Pfades von \( u \) zu \( x \) und des Pfades von \( u \) zu \( y \) sich genau um eins unterscheiden.
