Consider the lazy version of Prims algorithm that incrementally builds up a set A of edges as its solution. Recall that this version maintains a priority queue of edges which might contain multiple edges incident to each vertex not currently spanned by A. Using big-O notation, what is the worst-case runtime of this algorithm in terms of |V | and |E|?

(b) Using big-O notation, what is the worst-case runtime complexity of Kruskals algorithm in terms of |V | and |E|?

(c) Complete the characterization of Eulerian graphs: A graph is Eulerian if it has at most one nontrivial and all its vertices have .

(e) One implication of Kuratowskis theorem is that the complete bipartite graph Kx,y is not planar. What are x and y? That is, select the smallest x and y such that Kx,y is not planar.