<p>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.<br>
An O(VE) approach will be good for me .
Though i would prefer O(V^2) approach (if it is known)</p>

CC BY-SA 3.0
2015-07-12T13:45:51.970Z
The naive approach is to iteratively delete each vertex and check if the maximum matching is still the same size, which I guess gives $O(V^{1.5} E)$. Is $O(V^2)$ known even for finding a single maximum matching?
usul
CC BY-SA 3.0
2015-07-12T14:07:46.703Z
After Finding a single maximum matching we just need O(V+E) to find the answer. 
Also I read it somewhere , it is possible using Disjoint SET-Union DS for Edmond`s algo. Looking for an explanation.
Steven Anderson
<graph-theory><graph-algorithms>
Find the number of vertices that belong to all the maximum matchings of a general connected graph
Steven Anderson
# Find the number of vertices that belong to all the maximum matchings of a general connected graph

(Asked by: username_0 on 2015-07-12)

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)

**Tags:** graph-theory, graph-algorithms

> **Comments:**
> **username_1**: The naive approach is to iteratively delete each vertex and check if the maximum matching is still the same size, which I guess gives $O(V^{1.5} E)$. Is $O(V^2)$ known even for finding a single maximum matching?  
> **username_0**: After Finding a single maximum matching we just need O(V+E) to find the answer.  Also I read it somewhere , it is possible using Disjoint SET-Union DS for Edmond`s algo. Looking for an explanation.  

---

## 0 answers

