通过选择边数最少的顶点进行最大匹配的贪心算法？

Question

我正在学习 Blossom 算法，但我很困惑为什么你不能简单地采用我想到的这种贪心方法。有人有反例吗？

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

Answer 1

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

如果第一步你选择了BC，你就输了，因为你剩下2个奇数圈，你不能覆盖所有的顶点。最佳匹配是AB CD EF GH。