# Given undirected and connected graph G=(V,E). Prove for any DFS run: for any u,v∈V if u.d>v.d then u.d−v.d≥δ(u,v)

Given undirected and connected graph $$G = (V,E)$$. Prove for any DFS run: for any $$u,v \in V$$ if $$u.d>v.d$$ then $$u.d − v.d ≥ δ(u,v)$$

$$δ(u,v)$$-distance of a shortest path (not necessarily unique) in G

$$u.d,v.d$$-time, when each vertex was discovered in DFS for the first time.

I know that DFS not necessarily returns the shortest path.And I know that if $$u.d>v.d$$ then $$u$$ discovered after $$v$$, $$v≠u$$ and there is path is DFS between vertices, because G is connected.

I have tried to assume by contradiction that $$u.d-v.d<δ(u,v)$$

Given that G is connected and $$v.d. Then v discovered before $$u$$ and $$u≠v$$. According to the “parenthesis property” theorem: either $$u$$ is a descendant of $$v$$, or $$u$$ and $$v$$ do not exhibit an ancestor-descendant relation if $$G_π$$.

In the first case, $$u$$ is a descendant of $$v$$.

Let’s assume by contradiction that $$u.d-v.d<δ(u,v)$$ $$u.d-v.d$$ sets distance of simple path $$(u,v)$$ from $$u$$ to $$v$$ in $$G_π$$. Because $$u$$ is a descendant of $$v$$, the path $$(u,v)$$ also appears in $$G$$. By our assumption this distance is smaller then $$δ(u,v)$$ and that is in contradiction to the fact that $$δ(u,v)$$ is a distance of a shortest path (not necessarily unique) in $$G$$.

In the second case, $$u$$ and $$v$$ do not exhibit an ancestor-descendant relation if $$G_π$$.

Hence, $$u$$ was not discovered from $$v$$. It means that there is $$w≠v∈V$$ such that: $$w.d $$(w≠v)$$

$$w.d then $$u.d-w.d≥δ(u,w)$$ (proof of the first case) $$w.d then $$v.d-w.d≥δ(v,w)$$

And I have no idea how to continue from here..

• It can be pretty tricky writing down a proof unless you are very precise about 1) your dfs implementation 2) what words like "time", "discovered", "visited" mean – Matthew C Dec 3 '19 at 17:14
• Basically you have two cases: $v$ is discovered as a descendant of $u$ (easy), or not. In the latter case, if your DFS is implemented using a stack, this is like saying that $v$ is a descendant of some $w$, where $w$ was beneath $u$ in the stack – Matthew C Dec 3 '19 at 17:16
• @user111398 I cant prove the state in the latter case.. Do you have any clue? – sasha Dec 8 '19 at 15:22