Shortest path joining two paths on tree

56 Views Asked by At

Let $[a, b]$ and $[c, d]$ be two paths on a tree network with empty intersection. It is easy to observe that: The intersection of paths [x, y], where $x\in [a, b]$ and $y\in [c, d]$, is again a non-empty path, say $[r, s]$ here $r\in [a, b]$ and $s\in [c, d]$. Mathematically, we should have

$$\bigcap_{x\in [a, b], y\in [c, d]}[x, y] = [r, s]$$

We may think of $[r, s]$ as the "shortest path" joining $[a, b]$ and $[c, d]$. But I could not prove it! Is it a well-known result or I am just missing some assumption to prove it?

enter image description here

1

There are 1 best solutions below

5
On BEST ANSWER

Upon expanding on my comment, I noticed I could shorten the argument I sketched. This is the shortened version:

As a tree is connected, there are paths connecting $[a,b]$ and $[c,d]$. If we have some path $[r',s']$ connecting them, then we can find a sub-path $[r,s]$ such that $r \in [a,b]$, $s\in [c,d]$ and any other node on $y \in [r,s]$ is not in the union $y \notin [a,b] \cup [c,d]$. Also, we will assume that $[r,s]$ is fully reduced, i.e. does not visit any node twice. I will call such a path minimal.

Consider two such minimal $[r,s]$ and $[r',s']$ between the two segments $[a,b]$ and $[c,d]$. As $r,r'$ and $s,s'$ are connected to each other via the segments $[a,b]$ and $[c,d]$, we have two paths connecting $r$ to $s$, namely $[r,s]$ and $ [r,r'] \cup [r',s'] \cup [s',s]$. Both of these are fully reduced by our assumptions. But in a tree, fully reduced paths connecting the same endpoints are the same. Hence $r= r'$ and $s=s'$ and there is only one such path.

Hence we have shown the following: Any path connecting $[a,b]$ to $[c,d]$ contains the same minimal path $[r,s]$. Hence the intersection of all paths contains $[r,s]$. But trivially this path contains the intersection. Hence they are equal, which is what you wanted to prove.