1) Supposed at some stage in the breadth-first search algorithm the rooted tree has height h. Show that the next vertex added to the tree must be at height h or

h + 1.

2) With question 1, prove that every edge of the graph which is not in the breadth-first search tree joins vertices that are at most one level apart.