# Creating an algorithm which utilizes an already known optimal solution to max matching

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?

Let $$M$$ be a maximum matching of graph $$G = (V,E)$$. Let $$G'$$ be a new graph after adding a new vertex $$u$$ and the corresponding edges to $$G$$. Let $$M'$$ be a maximum matching of $$G'$$.
Create a flow network on graph $$G'$$ by creating new source and sink vertices. Send flow of value $$|M|$$ through the matching edges in $$M$$. Create a residual graph corresponding to this flow. If there is an augmenting path in the residual graph, then $$G'$$ has a matching of size $$|M|+1$$, otherwise not. The overall running time is $$O(|V|+|E|)$$.