The sum of distances from a vertex in a Tree to all other vertex have the same parity.

Question

Let $G$ be a tree on $n$ vertices when $n$ is even. Then for each vertex, the sum of distances from it to all other vertex is computed. It is interesting to note that all of them have the same parity.

I saw some examples of trees and the above fact holds true. But I am unable to prove that.

I was thinking if we can use the fact that there is always a unique path from one vertex to another in a tree.

Answer 1

For any connected bipartite graph $G=(A,B;E)$, $V(G)=A\cup B$, the following statement is true.

For any vertex $v\in A$ the sum of distances from $v$ to other vertices of the graph and $|B|$ have the same parity.

Therefore if we take a tree with odd number of vertices, not all such sums will have the same parity.

Edit.

If the number of vertices of the tree $G$ is even, then $G$ is a bipartite graph for which at any partition $V(G)=A\cup B$ the numbers $|A|$ and $|B|$ have the same parity. Therefore in this case the above sums will have the same parity. This immediately follows from the above statement.