Search code examples
algorithmgraph-theorygraph-algorithm

Greedy algorithm by selecting vertices with least number of edges for maximum matching?


I'm learning Blossom Algorithm, but I am confused why you can't simply do this greedy approach that I thought of. Does anyone have a counterexample?

While no more vertices:
    Choose the vertex (V) with the least number of edges
    Considering vertices connected to that vertex V, choose one with the least number of edges.
    Create this edge and don't consider these two vertices anymore. 
    Reduce the count of edges on each vertex accordingly. Repeat

Solution

  • E         G
    |\       /|
    | A-B-C-D |
    |/       \|
    F         H
    

    If at the first step you choose BC, you lose, because you are left with 2 odd cycles and you cannot cover all the vertices. The optimal matching is AB CD EF GH.