Graph theory.

Please do PROBLEM 3 and show step by step.

2: Suppose that T and T are both spanning tree of a connected graph G on n vertices. Lete E E(T)E(T) and let X and Y be a partition of V(G) such that e has one endpoint in X and the other endpoint in Y Prove that there exists an edge e' E E(T') \ E(T) such that e, has one endpoint in X and one endpoint in Y and such that Te- e' is a spanning tree of G. 3: Given a connected and weighted graph G on n vertices. Consider the following algorithm for costructing a minimum weight spanning of G. WeighLcxl and con ntx:i.cd maph G. IlIDEE.:: Initialization: Pick a arbitrary vertex v E V(G) and let Ho C G be the graph that contains only the vertex v. Iteration: For every i from 1 to n , pick the edge ei that has minimum weight over all the edges that have one endpoint in V(Hi-1) and one endpoint in V(G)\V(Hi-1). Add ej and the endpoint of ei in V(G)\V(Hi-1) to Hi-1 to create the graph Hi C G Output: T- Hn-1 () Prove that this algorithm always produces a minimum weight spanning tree. Hint: You can assume problem 2 is true and you should use it to prove that this algorithm, which is called Prim's algorithm, always produces a minimum weight spanning tree