https://manabitimes.jp/math/1147 上記記事で紹介されている、「最大マッチングでないなら増

Question

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に対する増加道ではないです。

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

@Konoito · Accepted Answer

【定義】

$P$ はマッチング $M$ に対する増加道

$\iff$

(1) $P$ の始点・終点が $M$ の頂点集合に属さない

(2) $M$ に属する辺と属さない辺とが $P$ には交互に現れる

【(1) 成立の確認】

$M$ の頂点集合は $V(M) := \{v_{11},v_{21},v_{12},v_{22}\}$ 。

$P$ の始点 $v_{13}$ および終点 $v_{23}$ はたしかに $V(M)$ に属さない。

【(2) 成立の確認】

$P$ は長さ $1$ の道だからこちらの条件成立は自明。

（「交互に現れる」の否定は「連続して現れる」だが、連続して現れるためには長さ $2$ 以上であることが必要）