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 at 21:25
  • $\begingroup$ How is the weight of a node defined? $\endgroup$ – Yuval Filmus Mar 14 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.