9780023606922, Chapter 2 6, Problem 28E

Prévia do material em texto

Chapter 2.6, Problem 28E Step-by-step solution Step 1 of 1 Proof of an expression Supposed expression is as follows. ≤ Here, T is a rooted tree with terminal vertices and height h and every vertex has at most 3 children. It can proof as above inequality by induction on h. STEP 1: For, consider the equivalent inequality n STEP 2: If the tree consists of a single vertex, in this case n=1 and thus Assume that the result holds for a tree whose height is less than h. Consider T be a rooted tree with a height terminal vertices where each vertex has at most 3 children. STEP 3: Suppose that the sub-tree's rooted at T's children have heights and n3 terminal vertices(If T has one child = = and if T has 2 children then =0and = STEP 4: The terminal vertices of T is equal to the sum of the terminal vertices of sub-tree's rooted at T's children. Hence, Using the inductive assumption, it can be written as Thus As heights of the sub-tree's rooted at T's children equal to h-1 The inductive step is verified and the proof is complete. Therefore, a rooted tree T with terminal vertices and height h and every vertex has at most 3 children then