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

Question

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?

Answer 1

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|)$.