1. Consider the following greedy algorithm for finding a maximum matching in a bipartite graph G =
Sort all the vertices in nondecreasing order of their degrees. Scan this sorted list to add to the current matching (initially empty) the edge from the list's free vertex to an adjacent free vertex of the lowest degree. If the list's vertex is matched or if there are no adjacent free vertices for it, the vertex is simply skipped. Does this algorithm always produce a maximum matching in a bipartite graph?
2. Design a linear-time algorithm for finding a maximum matching in a tree.