1. Consider the graph below: a b j i d 9 f (a) Starting with the matching M = {{c,d}}, iteratively extend M until a maximum matching is found. Do this by finding augmenting paths at each iteration. Avoid using trivial augmenting paths (that do not contain edges in the current matching) whenever possible. Show all working. (b) Find the edge-chromatic number of the graph by finding a minimum edge-colouring. Pro- vide an argument for how you know your solution is optimal. (c) Find a minimum vertex covering of the graph. (d) Compare your solutions to (a) and (c) and provide discussion and reasoning for the result. (e) Is the graph an interval graph? Provide reasons for your answer.