https://manabitimes.jp/math/1147

上記記事で紹介されている、「最大マッチングでないなら増加道が存在する」の証明が理解できません。

簡単な例を使って、定理で使用された方法を使って最大でないマッチングMと真の最大マッチングM'の対称差を求めてみたのですが、得られた辺の集合は増加道ではないように思います。

どこの解釈が間違っているかを調べたく、以下の例で解釈がおかしいところを指摘していただきたいです。

2部グラフG=(V1, V2, E)を考えます。

V1={v11, v12, v13}, V2={v21, v22, v23}, E={{v11,v21}, {v12,v22}, {v13,v23}}とします。

二つのマッチングM, M'を以下のように定義します。

M={{v11,v21}, {v12,v22}}, M'={{v11,v21}, {v12,v22}, {v13,v23}}

この場合、M'は最大マッチングになります。

このとき対称差MΔM'={{v13,v23}}

になり、パスですが、Mに対する増加道ではないです。

お手数をおかけしますが、どこが間違っているかご指摘いただければと思います。よろしくお願いいたします。