1

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

Leonard Neon
  • 1,354
  • Well, to prove the equality of two sets you have to prove two inclusions. Which one did you manage to prove and which one you find difficult? – Moishe Kohan Jan 14 '23 at 22:18
  • @MoisheKohan, I can't even show the existence of $[r, s]$. Anyway, if $r,s$ exist, then $\subset$ is clear. – Leonard Neon Jan 14 '23 at 22:22
  • But you wrote "easy to observe", did you mean it? – Moishe Kohan Jan 14 '23 at 22:29
  • sorry, what I actually mean is that: "from the figures, we see that ..." – Leonard Neon Jan 14 '23 at 22:34
  • Hint: You may start by showing that the intersection of two paths in a tree is either empty or again a path. Then you might try to show that the intersection of all those paths is non-empty. Then you could show that $(\bigcap [x,y]) \cup [a,b] \cup [c,d]$ is connected, which proves that $(\bigcap [x,y])$ connectes your two segments. Showing that its the shortest such path follows from the definition of $(\cap [x,y]) $ – Sven-Ole Behrend Jan 14 '23 at 22:37
  • @Sven-OleBehrend Thank you for your comment. Your first argument (in the hint) is ok for me. However, I have problem with the second one. To prove that the intersection is non-empty, I intended to use Helly's Theorem on tree. To do that, we need to show that the intersection of any two path (of the form [x, y]) is non-empty. This "simple case" is also extremely difficult (at least for me) since I/we do not know the condition for which the intersection is non-empty. – Leonard Neon Jan 14 '23 at 22:46

1 Answers1

1

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.

Sven-Ole Behrend
  • 1,473
  • 1
    I appreciate your answer. However, we should be very careful with this problem since it is easy to get mistake with this problem. The first flaw in your argument is that: "how can you show the existence of the minimal path?". The second flaw is that the statement: "In a tree, fully reduced paths connecting the same endpoints are the same" is not correct (is there a definition for "reduced path"). – Leonard Neon Jan 15 '23 at 07:56
  • (continue of my comment) Take a star graph with 3 leafs a, b, c, with root p as an example: To go from a to b, we have two options: $[a, b] = a--> p--> b$ and $[a, c]\cup [c, b] = a-->p-->c--> p--> b$. But $[a, b]$ and $[a, c]\cup [c, b] $ are not the same. – Leonard Neon Jan 15 '23 at 07:56
  • 1
    This is what I mean by a fully reduced path, a path which visits each node only once. Your first path is reduced, while the second one isn’t. It visits p twice. Any non-reduced path can be shortened to a fully reduced path with the same endpoints. If you shortened your path $[a,c] \cup [c,b]$, you would get the path $[a,b]$. – Sven-Ole Behrend Jan 15 '23 at 08:45
  • 1
    that's great, i will try to find the definition of fully reduced path and comeback soon, 1 upvote for now – Leonard Neon Jan 15 '23 at 08:48
  • 1
    yeah I now find a proper definition of a path (what you refer as fully reduced path). According to wiki: "In graph theory, a path in a graph is a finite sequence of edges which joins a sequence of vertices, on which the edges are all distinct". Using this kind of definition of path, I am now able to show the existence of your "minimal" path. Big thank! – Leonard Neon Jan 15 '23 at 09:35