Skip to content
Quantoros

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

Related questions