Proof
(related to Lemma: Coloring of Trees)
- By hypothesis, let $G(V,E)$ be a tree.
- According to equivalent definitions of trees, for every pair of vertices $u,v\in V$ there is exactly one path $P^k:=x_0x_1\ldots x_{k-1}x_k$ in \(G\) with $x_0=u$ and $x_k=v.$
- It is obvious, that any $P_k$ in $G$ can be 2-colored, because we can alternate the to colors.
- Starting at the root of the tree with first color and alternating with the second color along each path from the root to the leafs of the tree completes the proof.
∎
Thank you to the contributors under CC BY-SA 4.0!
- Github:
-
References
Bibliography
- Piotrowski, Andreas: Own Research, 2014