A matching is a collection of edges, no two of which share an endpoint. A matching M = {ei} is maximal for inclusion if there is no other matching M' so that M M' 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 2|M| 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 Suc*. 1. Give an algorithm that finds a maximal for inclusion matching M, in polynomial time. 2. Consider a set W that contains the 2|M| 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 Suc*