GRAPHS

1. [5 marks]. Consider the following rooted tree:

e

h'

(i) What are the children of c? What are the ancestors of h?

Now suppose we given any rooted tree whatsoever:

(ii) What kind of vertex has the fewest number of ancestors? No justification is needed.

(iii) What kind of vertex has the greatest number of ancestors? Justify your answer carefully. [Hint:

proof by contradiction.]