Find the number of vertices that belong to all the maximum matchings of a general connected graph . The given graph is connected but not necessarily bipartite. Please describe the complete approach with useful links , I read stuff related to augmenting paths but could not comprehend well.
An O(VE) approach will be good for me .
Though i would prefer O(V^2) approach (if it is known)
 A: Perhaps there are some other solutions, but the simplest I can think of needs an understanding of the concept of augmenting paths. I don't know how much it will be useful to you, nevertheless I will post some hints, maybe it will clear some things.
Hint:


*

*The basic approach is to calculate for each $v \in V$ a maximum cardinality matching in $G_v = G \setminus_V \{v\}$, that is, a graph $G$ without $v$. If the cardinality of the matching decreases, that means $v$ has to be in all of them.

*You can observe that the above approach repeats itself a lot, to avoid it, we can first start with calculating some maximum cardinality matching $M$ for the whole graph $G$.

*Now, for each $v \in V$ you have three cases:


*

*$v \notin V(M)$: $M$ is a witness that $v$ does not belong to all maximum cardinality matchings.

*There is an augmenting path from $u$ in $G_v$ with matching $M \setminus \{u,v\}$, where $u$ is the pair of $v$ in $M$: this new matching is a witness that $v$ does not belong to all maximum cardinality matchings.

*There is no such an augmenting path: which proves via this lemma that maximum matching in $G_v$ has strictly smaller cardinality.


*You can observe that the last bullet still repeats itself a lot, that is, a lot of augmenting paths may end up in the same $M$-free vertex. Hence, instead of calculating augmenting paths from matched vertices you can search them from the other side, the vertices which are free in $M$.

*Finally, rather than starting the search from each free vertex separately, you can first merge them all into one super-source, where the whole approach simplifies down to calculating the even/odd level of each vertex.


I hope this helps $\ddot\smile$
