# Prove $|d_{s}(u)-d_{s}(v)|\leq1$ in BFS

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?

There is at least one edge $$w \in V$$
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).