1
If you take $S$ to be the sum of all the weights on all the edges in the graph and you add $S$ to all the weights in the graph, then a regular maximum weight matching will find you the matching you are looking for, since now with the large weights on all the edges, it will prefer a matching that uses the most number of edges first.
In your example of 1--2--3-...
Only top voted, non community-wiki answers of a minimum length are eligible
