2
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

The statement is false. Take a look at the following graph:

enter image description here

In one BFS run, you will get the following tree:

enter image description here

That has a distance of $1$ between $u$ and $v$, while in a different run, you could get another tree:

enter image description here

Which has a distance of $3$ between $u$ and $v$

$\endgroup$
1
  • 1
    $\begingroup$ 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). $\endgroup$
    – Steven
    Jul 22 at 19:28
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.