TADM2E 5.3

From Algorithm Wiki
Revision as of 18:22, 11 September 2014 by Algowikiadmin (Talk | contribs)

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
Jump to: navigation, search

Induction proof:

Base case: Tree composed of just two nodes: x(root) and y. There is only one way x -> y

Assuming there is an unique path between x and y, we add a new leaf z under y. z is only connected to its parent y, so there is only one way from z to x that is z -> y->[unique path assumed]->x