Edmond's blossom algorithm computes a maximum weight matching in a general graph (https://en.wikipedia.org/wiki/Blossom\_algorithm).
Many papers also reference to Edmond's blossom algorithm to compute a Maximum weight *perfect* matching. I don't understand how this is possible. Given for instance the following graph (a square with one diagonal):


V={0,1,2,3}, E={(0,1),(1,2),(2,3),(3,0),(0,2)}. All edges have weight one, except the diagonal edge (0,2) which has weight 10.


A maximum weight perfect matching would be M1={(0,1),(2,3)} with weight 2. However a maximum weight (non-perfect) matching in the same graph would be M2={(0,2)} with weight 10.
So how can the same algorithm be used to compute a perfect matching?


See for instance the introduction in the following papers:


1. [Kolmogorov
Blossom, V: a new implementation of a minimum cost
perfect matching algorithm](https://pdfs.semanticscholar.org/930b/9f9c3bc7acf3277dd2361076d40ff03774b2.pdf)
2. [Cook, Rohe, Computing Minimum-Weight Perfect Matchings](http://www.math.uwaterloo.ca/~bico/papers/match_ijoc.pdf)



Edmond's blossom algorithm for Max weight perfect matchings
Suppose you have a graph with edge weights $w\_e$. Add constant $M > \sum\_e |w\_e|$ to all the weights, obtaining $w'\_e = M + w\_e$. If there is a perfect matching, its (primed) weight is greater than the (primed) weight of any non-perfect matching. Thus the matching of maximum (primed) weight is a maximum-weight perfect matching.


