PLEASE do question 4 and show it all Step by step.

Problem-4: (3 +5 + 2 + 5 + 5 = 20 Marks] (a) Draw an undirected connected graph with nine vertices and at least15 edges. The vertices should be called A, B, C, D, E, F, G, H and I. There must be at least 2 paths of length three from D to H and a path of length two from B to I. (b) Show breadth-first traversal of the graph constructed in part (a), where G is the starting node. Visit adjacent nodes in a clockwise ordering from a particular node (12 o'clock position). Show each step to find the traversal sequence using the appropriate data structure. (c) Convert the graph of part (a) into a weighted graph by assigning weights to each of the edges of the graph; ranging 1 - 20 (randomly pick any value). Do not assign the same weight to more than 2 edges. (d) Construct the minimum spanning tree for the weighted graph constructed in part (c). Also compute the weight. Show the steps you applied to construct the minimum spanning tree. (e) Use Dijkstra's algorithm to calculate minimum cost path (Show detail steps), for the weighted graph constructed in part (c), to travel from node H to all other nodes and show the corresponding routes