title: Maximum matching in general graph
body: <p>I am trying to learn <a href="https://en.wikipedia.org/wiki/Blossom_algorithm" rel="nofollow">Blossom's algorithm</a> for maximum matching.
  Basically the algorithm works in the following way: </p>
  
  <ul>
  <li>1) find an augmented path in the graph</li>
  <li>2) remove the matched edges in this path, and include the unmatched edges in the path to our matching.</li>
  <li>We repeat these steps until there exists an augmented path.</li>
  </ul>
  
  <p>The maximum size of maximum matching can be V/2 and we can find an augmented path in O(E+V) by doing a dfs. So every time we find an augmented path, the size of the matching increases by 1. So I need to find an augmented path at most V/2 times, so the time complexity is O(V * E + V * V),</p>
  
  <p>But, in the Wikipedia page for blossom's algorithm, it is given that we need to contract the odd cycles of alternating matched edges and find augmented path, And also time complexity is given to be O(E * V * V).</p>
  
  <p>So can anyone please correct me, what am I doing wrong?</p>