Please analyze the complexity of the algorithm also.

Question 3: Recall that a matching is a collection of edges, no two of which share an endpoint. A matching M = {e} is maximal for inclusion if there is no other matching M' so that M CM' and M+M'. 1. Give an algorithm that finds a maximal for inclusion matching M, in polynomial time. 2. Consider a set W that contains the 2M vertices of a maximal matching M. Show that this set is a vertex cover in the graph. 3. Let uc be the size of the smallest vertex cover in the graph. Show that for any matching M, M