2-Coloring a tree with $2n$ vertices with additional constraint 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.
 A: 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.
A: It's in general not possible. Take the simple tree with one root $r$ and three child leaves $c_1,c_2,c_3$. If we take $V=\{(r,c_1),(c_2,c_3)\}$ we can't get a 2-coloring as you want. If $c_2$ and $c_3$ have a different color, $r$ - which is neighbor of $c_2$ and $c_3$ - needs a third color so that it works out.
Or do you have more constraints on the tree or on the set $V$?
