1. 10 points Prove that given a graph G with two distinct nodes s and t, if every path between s and tis > n/2 then in the BFS tree where s is the root, at least one level in that tree has only one node. Help: Consider the roots at level O, the set of s's children level 1 and so on. n is the number of vertices in the graph. A path of length m between two vertices a and b means there are m edges between the two vertices. Example: The path a-x-y-w-b is of length 4