# There exists some number $x$ so in any run of BFS from vertex $w$, so the distance from $u$ to $v$ in BFS tree is always $x$

Studying for my finals and stuck on the following question:

Prove or disprove: Given an undirected and connected graph $$G=(V,E)$$ and three different vertices $$u,v,w\in V$$ then there exists some number $$x$$ so in any run of BFS from vertex $$w$$, the distance from $$u$$ to $$v$$ in BFS tree is always $$x$$.

I think it's not true but could not think about a good example to disprove it.

The statement is false. Take a look at the following graph: In one BFS run, you will get the following tree: That has a distance of $$1$$ between $$u$$ and $$v$$, while in a different run, you could get another tree: Which has a distance of $$3$$ between $$u$$ and $$v$$

• A small remark: here the trees are depicted with directed edges going from a vertex to its parent, but the actual trees are undirected (hence the distance between $u$ and $v$ is always well-defined). Jul 22 at 19:28

Because you run BFS from $$w$$, The BFS produce a shortest path tree $$\mathcal{T}$$ that contain shortest path from $$w$$ to other vertices. On the other hand the claim say that: any tree $$\mathcal{T}$$ that produced by BFS, the distance between $$u,v$$ is $$x$$, clearly it's not true, because the BFS guarantee the distance between $$w$$ and $$\forall v\in V\setminus w$$ that by multiple running BFS from $$w$$ not changed, but the distance between any two other vertices can be changed. BFS can't guarantee that distance between any two other vertices $$u,v\in \{V\setminus w\}$$ remain as the same previous run of BFS. Look at the counter-example nir shahar.