HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

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$

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
fromnumberthevertexanybfsdistancealwayssomeexists

Problem

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.

Solution

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$

Context

StackExchange Computer Science Q#142569, answer score: 3

Revisions (0)

No revisions yet.