Pruning a Tree In order to prove theorems about trees, it is helpful to introduce the process of pruning a tree: This means removing a vertex of degree 1 from the tree along with the edge that occurs at that vertex. However, the other endpoint of that edge remains in the tree. Thi:s step can then be repeated any number of times. Example of pruning a tree A BC D B C D B C D E F E F B C D D5 Pruning Lemma Prove that on each step of the pruning process, when one verterx and one edge are removed from a tree, the remaining graph is still a tree. Use the definition of a tree. We need another fact: that every tree with more than one vertex can be pruned. This fact depends on the existence of a vertex of degree 1 in the tree. D6 Lemma on Vertices of Degree 1 Prove that every tree with two or more vertices has at least two vertices of degree 1. (Suggestion: Consider a longest simple path in the tree. What must be true about its endpoints, and why?) Pruning a Tree In order to prove theorems about trees, it is helpful to introduce the process of pruning a tree: This means removing a vertex of degree 1 from the tree along with the edge that occurs at that vertex. However, the other endpoint of that edge remains in the tree. Thi:s step can then be repeated any number of times. Example of pruning a tree A BC D B C D B C D E F E F B C D D5 Pruning Lemma Prove that on each step of the pruning process, when one verterx and one edge are removed from a tree, the remaining graph is still a tree. Use the definition of a tree. We need another fact: that every tree with more than one vertex can be pruned. This fact depends on the existence of a vertex of degree 1 in the tree. D6 Lemma on Vertices of Degree 1 Prove that every tree with two or more vertices has at least two vertices of degree 1. (Suggestion: Consider a longest simple path in the tree. What must be true about its endpoints, and why?)