Suppose given a tree $\mathcal{T}$ with $n$ pair of vertices $V=\{(p_0,q_0),\dots,(p_n,q_n)\}$ . According to this link we know that any tree can be colored by $2$ colors. But my problem is as follow:
I want coloring $\mathcal{T}$ with 2 colors such that each pair $(p_i,q_i)$ has different color. Are there any proof or paper that show us it's possible or not? Thanks.
Best Answer
Such a coloring exists if and only if the distance between any of the $(p_i,q_i)$ is odd. The distance between two vertices is the number of edges in a shortest path between them.
Proof Suppose that indeed all such distance are odd, and color the tree $\mathcal{T}$. Take a path from $p_i$ to $q_i$, say $p_i,v_1,\ldots, v_k, q_i$. As the coloring of the tree is proper, $v_1$ has a different color than $p_i$, and $v_2$ has a different color than $v_1$, etc. As the path will have an odd number of edges, $k$ is even, and so $v_k$ has the same color as $p_i$ and $q_i$ has different color then $v_k$. So $p_i$ and $q_i$ have different colors.
Now suppose that the distance from $p_i$ to $q_i$ is even, and let $p_i,v_1,\ldots, v_k,q_i$ be the path connecting them with $k$ odd. Suppose that we have a proper coloring of the tree where $p_i$ and $q_i$ have different color. Then $v_1$ and $v_k$ must also have different colors. And $v_2$ and $v_{k-1}$ must also have different colors, etc. And $v_{(k-1)/2}$ and $v_{(k+1)/2+1}$ must also have different colors. But then there is no color that $v_{(k+1)/2}$ can have that is distinct from the colors of these last two vertices.