Consider the following algorithm, BruteForceEdgeConnectivity, which returns the edge connectivity of a graph. Assume that the function isConnected returns true or false based on whether or not a graph is connected. Recall that n refers to the number of vertices in G.

a. On what graphs, if any, does BruteForceEdgeConnectivity reach the final return statement?

b. On what type(s) of graphs does the worst-case time behavior occur?

c. Given that isConnected takes T(n) time, and where (G) denotes the (maximum) edge connectivity of the input graph, what is the time complexity of BruteForceEdgeConnectivity as a function of (G) and T(n)?

Brute Force EdgeConnectivity (G) If not isConnected (G) Return 0 For k 1 to n For each set S of k edges in G If not is connected (G S) Return k Return 0