1
$\begingroup$

Trying to prove the following problem:

Given a graph $G=(V,E)$ and vertex $s\in V$, prove that: $\forall (u,v)\in E,\ |d_{s}(u)-d_{s}(v)|\leq1$ where $d_s(v)$ is the shortest path from $s$ to $v$ in BFS.

What I did: Let assume that it's isn't true, meaning there is $(u,v)\in E$ so $|d_{s}(u)-d_{s}(v)|>1$. Lets run BFS on graph $G$. If in BFS process there is edge $(u,v)$, this means that $d_{s}(u)+1=d_{s}(v)$ so $|d_{s}(u)-d_{s}(v)|=1$ which contradicts $|d_{s}(u)-d_{s}(v)|>1$. This means that there is at least one edge $w\in V$, in the path from $u$ to $v$.

Now I'm stuck. I don't come empty handed, I have the following theorems:

  1. Given graph $G=(V,E)$ and vertex $s\in V$, for each edge $(u,v)\in E$ we have $\delta\left(s,v\right)\leq\delta\left(s,u\right)+1$ where $\delta(s,v)$ is the shortest path between $s$ and $v$ (or $\infty$ if no such path) in graph $G$ (note the difference between $\delta$ which on $G$ and $d$ which on BFS).
  2. For each vertex $v\in V$ we get $d(v)=\delta(s,v)$ in BFS.

I think I might need to use those two theorems here but I don't see it. My problem is that there is at least one vertex $w$ and not exactly one. How can I prove it?

$\endgroup$
0

1 Answer 1

1
$\begingroup$

First of all your question is quite confusing:

There is at least one edge $w \in V$

Is it an edge or a vertex?

Maybe it would be easier for you to look at some edge $(u,v) \in E$ and think about the moment in time $\tau$, when the BFS algorithm reached either $u$ or $v$ for the first time (it could reach them both at the same time).

$\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.