Assume that there is a maximal matching of size k in an bipartite graph, G=(U,V,E). I now want to utilize this maximal matching in order to find a maximal matching in the bipartite graph where we add some node u to U and some edges (u,v_1),...,(u,v_n), where v_1,...,v_n are vertices in V.
I have figured out that such an extension may yield a maximal matching of maximum size k+1. Thus I want to formulate an algorithm which finds a maximal matching of size k+1, if one exist. It is clear that if such a matching exist, then it must include the added vertex u. If there exist some v, adjacent to u that is not included in the optimal solution of size k, then we are done as we found a maximal matching of size k+1. In the case where there are no "available" adjacent vertices. Firstly we have to remove some pair which includes one of the occupied adjacent node and connect it with u instead. We now have to rearrange the matching in some clever way, but I'm not sure how to proceed from here, any suggestions?