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<u.d$. Then v discovered before $u$ and $u≠v$. 180
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<v.d<v.f<u.d<u.f<w.f$ $(w≠v)$
$w.d<u.d$ then $u.d-w.d≥δ(u,w)$ (proof of the first case) $w.d<v.d$ then $v.d-w.d≥δ(v,w)$
And I have no idea how to continue from here.. 433