Suppose we generate a BFS tree rooted at vertex $s$ on an undirected graph $G$. Let $x$ and $y$ be two vertices in this tree (and it's possible for $x=y$), where their distance computed by BFS are $d_x$ and $d_y$, resp.
What are the max and min possible values of $\text{dist}_G(x,y)$, the distance in $G$ between $x$ and $y$, given $d_x$ and $d_y$?
So far, I have a lower bound of
$$\mid d_x - d_y\mid \leq \text{dist}_G(x,y).$$
But I'm confused when trying to find the upper bound, does $\text{dist}_G$ imply the shortest path between $x$ and $y$ or do we have to account for redundancies?
In any graph $G$, the path from $x$ to $y$ going through $s$ is of length $d_x + d_y$, giving us an upper bound for $d_G(x,y)$.
To prove the upper bound is the best we can hope for, consider the case when $G$ is an odd path (odd vertices, even length). Let $x$ and $y$ be its endpoints and the starting point s be the middle point, such that $d(x,s)=d(y,s)$.
Then, $d_x=d(x,s)=d(y,s)=d_y$ and $d_G (x,y) = d_x + d_y$ (because the only path from $x$ to $y$ passes through $s$), so the upper bound is reached, thus it has to be at least $d_x + d_y$.
I'm not sure what you mean in the last question, I assume $dist_G$ means the distance from $x$ to $y$ in $G$ (not necessarily in the BFS tree).