9780023606922, Chapter 2 6, Problem 20E

Prévia do material em texto

Chapter 2.6, Problem 20E Step-by-step solution Step 1 of 3 Consider a rooted tree T with vertices. Consider two vertices in the rooted tree that have the same parent. Step 2 of 3 Tree: - If V and W are vertices of a simple graph T and there is a unique simple path that is there are no repeated vertices from V and W, then T is a tree. Also a tree is an acyclic graph. A Rooted tree is a tree in which a particular vertex is designated as root so that all other vertices are placed under that vertex. Parent of a vertex:- If T is a tree with root and there is a simple path in T. Then the parent of is Step 3 of 3 Since the 2 vertices have same parent then there exists a unique simple path between the 2 vertices. Since they have the same parent they are siblings. For example, in the following tree:- 5 (root) 2 7 4 6 9 1 3 8 10 Since, vertices 7 and 2 have a common parent both the vertices are siblings. Therefore, two vertices having same parent are siblings.