9780023606922, Chapter 2 6, Problem 11E

Prévia do material em texto

Chapter 2.6, Problem 11E Step-by-step solution Step 1 of 2 Consider a rooted tree If T has a root and no edges, the diameter and the height of the tree, both are zero and the above statement will be true. So, assume that T has at least one edge. Assume P be the shortest path of maximum length, according to the definition of a diameter: and W are vertices in where G be a graph and V and W are vertices. So, P is the diameter of T. Now, as P is the longest shortest path, its one end vertex must be a terminal vertex. Assume that P begins at the terminal vertex. Also, P moves towards the root through edges moving up and then P have zero or more edges away down from the root. Step 2 of 2 The number of up edges is less than or equal to the height of T but the number of down edges is less than the height of So, then its obvious that the diameter of T is less than or equal to twice of the height of the tree. Hence, we proved that the diameter of the tree is less than or equal to twice of the height of the tree.