i. Explain what property of trees it would violate if there was more than one path...

 

Transcribed Image Text:

i. Explain what property of trees it would violate if there was more than one path between two vertices in a tree. ii. Let G = (V,E) be a tree. Prove G has |V|- 1 edges using strong induction. Hint: In the inductive step, choose an edge (u, v) and partition the set vertices into two subtrees, those that are reachable from u without traversing (u, v) and those that are reachable from v without traversing (u, v). You will have to reason why these subtrees are distinct subgraphs of G. iii. What is the total degree of a tree? i. Explain what property of trees it would violate if there was more than one path between two vertices in a tree. ii. Let G = (V,E) be a tree. Prove G has |V|- 1 edges using strong induction. Hint: In the inductive step, choose an edge (u, v) and partition the set vertices into two subtrees, those that are reachable from u without traversing (u, v) and those that are reachable from v without traversing (u, v). You will have to reason why these subtrees are distinct subgraphs of G. iii. What is the total degree of a tree?