I tried following strategy (though I never got it correct though later on applied on the edmond blossoms algorithm) for the problem SEAGRP in January Long Challenge 2014. Can anybody point out why is this algorithm incorrect?
- As I already know the graph I know the degree sequence of the graph(Obtained by removing multiple edges between same set of nodes as they don’t have any effect).
- The Final graph is a perfect matching so the degree sequence of each vertex in the resultant graph i s 1,1,1,1,…
- So If we subtract the degree sequence 1,1,1… from the degree sequence of the graph given we will get the degree sequence of the graph which needs to be subtracted from the original graph to make it a perfect matching.
- So on getting the degree sequence of the remaining graph I tried to prove it graphic by Havel Hakimi theorem.