Consider a bipartite graph G = (U, V, E) on 2n vertices that contains a perfect matching. Suppose the vertices in U arrive in an online fashion and the edges incident to each vertex u ? U are revealed when u arrives. When this happens, the algorithm may match u to a previously unmatched adjacent vertex in V , if there is one. Such a decision, once made is irrevocable. The objective is to maximize the size of the resulting matching.

Consider the algorithm that always matches a vertex in U if a match is possible. Show that this algorithm achieves a competitive ratio of 1/2.