Let be the number of steps taken starting from node . It is sufficient to show that for any two adjacent nodes and .
What happens when we change our root from to ? First, consider the second step: the shortest path to all nodes in decreases, while the shortest path to all nodes in increases (here, denotes the subtree rooted at ). Therefore, the contribution of the second step increases by , where denotes the size of subtree .
What about the first step? Let be the expected time to leave subtree given that you start at node .
Lemma
For every subtree , .
Proof: We induct. If , this claim is obvious.
Otherwise, let be the degree of node . Then, we expect to visit times before finally leaving, which means we will start from and come back times. In each trip, we move to each of our children with equal probability. Therefore, we have
where denotes a child subtree of .
To finish, notice that when moving our root from to , the contribution from the first step increases by and decreases by . Expanding this out, the net change to this contribution is
which exactly cancels out the change in contribution from the second step!