How do I prove that $d(x,y)$, defined as the weight of the lowest common ancestor of $x,y$, satisfies the strong triangle inequality:

$$ d(x,y) \le \max(d(x,z), d(y,z)) $$

How do I even start such a proof?

  • 1
    $\begingroup$ Start by trying some examples. Then you'll probably realize that there is a case analysis based on the relative locations of their LCAs. Try all cases. $\endgroup$
    – D.W.
    Mar 13, 2021 at 21:25
  • $\begingroup$ How is the weight of a node defined? $\endgroup$ Mar 14, 2021 at 6:12


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.