In a rooted tree, vertices u and v have a common descendant. Must one be an ancestor of the other? Would the statement…
Quant ResearchLevel: IntermediateAncestor comparability
In a rooted tree, vertices u and v have a common descendant. Must one be an ancestor of the other? Would the statement hold in a directed acyclic graph?
Hints
- Use uniqueness of the root-to-descendant path.
- Look for merging paths when constructing a DAG counterexample.
Answer
In a tree yes: both lie on the unique path from the root to that descendant, so they are ordered along it. In a DAG no: a diamond with root splitting to u,v and both joining at w gives incomparable ancestors of w.
Source and licence: Oscar Levin — Discrete Mathematics: An Open Introduction, 3rd edition · CC-BY-SA-4.0 · answer: Quantoros editorial