Question from my book:
Show that if two distinct vertices in a rooted tree, u and v, have a common descendant, then vertex u is a descendant of v or vertex v is a descendant of u. You can assume that every vertex in a rooted tree has a unique path to the root.
Intuitively and graphically, this makes sense. I have no clue how to prove this rigorously, though. I got this far:
suppose $y$ is a descendant of $u$
suppose $y$ is also a descendant of $v$
then $u$ must be an ancestor of $y$, and $v$ must also be an ancestor of $y$
I'm missing the final link. How can I claim that $u$ is an ancestor of $v$ or vice versa? I'm thinking I have to use paths, but it's not too clear how I can do that. Here's what I was thinking for that as well:
- arbitrary path from root $r$ to $y$ must pass through $u$ and $v$: $<r, *, *, *, u, *, *, v, *, y>$
That's all I got :/
Assume $v_1,v_2$ are two vertices with the common descendant $u$, and $r$ is the root. Lets denote by $P_x$ the unique path from $x$ to $r$. Note that $x$ being a descedant of $y$ means exactly that $y\in P_x$.
Because $v_1$ and $v_2$ are both ancestors of $u$, we have $v_1,v_2\in P_u$. Going along $P_u$ from $u$ to $r$, we encounter one of the vertices $v_i$ first, w.l.o.g. say it is $v_1$. Then the subpath $v_1P_ur\subseteq P_u$ is a path from $v_1$ to $r$ (hence the unique one) containing $v_2$. Thus, $v_2\in P_{v_1}$ and therefore $v_1$ is a descedant of $v_2$. Equivalently for the case when $v_2$ is encountered first. $\quad\square$