# Question: given a rooted tree t v e r where...

###### Question details

Given a rooted tree T = ((V, E), r) where r ∈ V is the root of T, we define the following notions.

Definition 1. A path in T is a sequence of vertices x1, . . . , xn ∈ V such that (xi, xi+1) ∈ E for all i < n (i.e.,

there is an edge between xi and xi+1) and such that all xi are distinct, except possibly for x1 and xn vertices.

Definition 2. The child relation RC ⊆ V × V is defined for all x, y ∈ V such that (x, y) ∈ RC (i.e., x is a child

of y) if and only if there exists a path r, . . . , y, x in T.

Definition 3. The descendantrelation RD ⊆ V ×V is defined, recursively, for all x, y ∈ V such that(x, y) ∈ RD

(i.e., x is a descendant of y) if and only if either (a) (x, y) ∈ RC (i.e., x is a child of y); or (b) there exists a vertex

z ∈ V such that (x, z) ∈ RC (i.e. x is the child of z) and (z, y) ∈ RD (i.e., z is a descendant of y).

Prove, by induction, that if v0, . . ., v ̇ n is a path in tree T, with n ≥ 1 and v0 = r (i.e., a path from the root vertex r

to vertex vn), then (vn, vm) ∈ RD, for all 0 ≤ m ≤ n−1 (that is, vn is a descendant of every verted v0, ..., vn−1).