Problem 4: Depth First Search 20 points) (a) (10 points] During the execution of depth first search, we refer to an edge that connects a Vertex to an ancestor in the DFS-tree as a back edge. Either prove the following statementor provide a counter-Example: if G is an undirected, connected graph, then each of its edges is either in the depth-first search tree or is a back edge. (b) (10 points] Suppose C is a connected undirected graph. An edge whose removal disconnects the graph is called a bridge. Either prove the following statement or provide a counter- example: every bridge e must be an edge in a depth-first search tree of G. Problem 4: Depth First Search 20 points) (a) (10 points] During the execution of depth first search, we refer to an edge that connects a Vertex to an ancestor in the DFS-tree as a back edge. Either prove the following statementor provide a counter-Example: if G is an undirected, connected graph, then each of its edges is either in the depth-first search tree or is a back edge. (b) (10 points] Suppose C is a connected undirected graph. An edge whose removal disconnects the graph is called a bridge. Either prove the following statement or provide a counter- example: every bridge e must be an edge in a depth-first search tree of G