2. (10 pts) Consider the following graph. G (V, E), V-(a, b, c, d, e, f, g, h, i a,b), (a,d), (a,e), (b,c), (c,e), (c,f), (d,e), (d,g), (d,h), (e,f), (eh), (e,i) (g,h), (h,i)} It is edge-weighted by the following function. w:EZ+, w(a,b): 1, w(a,d): 3, w(a,e)-3, w(b,c):2, w(c,e):2, w(c,h-1, w(d,e)-3, w(d,g)-1, w(d,h)-2, w(e,f)-3, w(e,h)-4, w(e, i)-4 w(g,h)-3, w(h,i)-1 Draw the graph G as a figure and insert it below. Then run the MST algorithm given in class on G to construct a minimum spanning tree of G. Color in red the edges of the obtained spanning tree. You can insert a separate figure, or show your work in the figure for a. What is the total edge weight of the minimum spanning tree? How many spanning trees of the minimum weight does G have? Justify your answer in English in more than 3 and less than 15 lines. You can use the following proposition a. b. c. d. Proposition: The algorithm MST(G) given in class can produce any minimum spanning tree of G Answers: 2-a, 2-b: Insert one or two figures below 2-c: ...write your answer here... 2-d: write your answer here, and justification below