Edmondsの花アルゴリズム

$B$ の頂点を閉路の順に $c_0=b,c_1,\dots,c_{2k}$ と並べる。$M\cap E(B)$ は $b$ を飽和しない $B$ のマッチングで $k$ 本からなるので、$\{c_1c_2,c_3c_4,\dots,c_{2k-1}c_{2k}\}$ である。$v=c_j$ のとき、$j$ が偶数なら $R=c_0,c_1,\dots,c_j$、$j$ が奇数なら $R=c_0,c_{2k},c_{2k-1},\dots,c_j$ であり、どちらも $b$ から $M$ に属さない辺で始まり、長さが正なら $v$ で $M$ の辺で終わる $M$ 交互道である。
1：$Q$ が $\beta$ を通らなければ、$Q$ の辺と頂点は $G$ でも同じで、$M$ 増加道である。$Q$ が $\beta$ を通るとする。$\beta$ が $Q$ の内部の頂点なら、$\beta$ には $Q$ の辺が 2 本接続し、一方は $M/B$ の辺 $z\beta$ で、これは $M$ の辺 $zb$（$z\notin V(B)$）から来る。もう一方が $y\beta\notin M/B$ である。$\beta$ が $Q$ の端点なら、$\beta$ は $M/B$ 露出点なので $b$ は $M$ 露出点で、$\beta$ の $Q$ の辺は $y\beta\notin M/B$ だけである。どちらの場合も、$Q$ の $\beta$ を $R$ に置き換えた列（内部なら $\dots,z,b,\dots,v,y,\dots$、端点なら $b,\dots,v,y,\dots$）は $G$ の道で、頂点は相異なる。交互性を確かめる。$b$ では $M$ の辺 $zb$ の後に $R$ の最初の辺（$M$ に属さない）が来る。$R$ の最後の辺は $v$ の $M$ の辺で、その後の $vy$ は $M$ に属さない（$v\neq b$ なら $v$ の $M$ の辺は $B$ の上にあり、$v=b$ なら $b$ の $M$ の辺は $zb$ で $y\neq z$）。$R$ の長さが $0$ なら、$zb\in M$ の後に $by\notin M$ が来る。端点は $M$ 露出点のままである。よって $M$ 増加道である。
2：1 と マッチング(グラフ理論) の定理「Berge の定理」により、$M$ が最大なら $M/B$ も最大である。逆を示す。
まず $b$ が $M$ 露出点の場合を示す。$M$ が最大でないとすると、$G$ に $M$ 増加道 $Q$ がある。$Q$ が $B$ と交わらなければ、$Q$ は $G/B$ の $M/B$ 増加道である。交わるとする。$Q$ の両端点は $M$ 露出点で相異なり、$B$ の $M$ 露出点は $b$ だけなので、少なくとも一方の端点 $w$ は $B$ の外にある。$Q$ を $w$ からたどって最初に出会う $B$ の頂点を $u$ とし、$w$ から $u$ までの部分を $Q'$ とする。$Q'$ の $u$ に入る辺 $xu$ は $M$ に属さない（$u\neq b$ なら $u$ の $M$ の辺は $B$ の上にあり、$u=b$ は露出点）。このとき $x$ の $M$ の辺は（あれば）$Q'$ の手前の辺で、その相手は $B$ の外にあるので、$x\beta\notin M/B$ である。よって $Q'$ の $u$ を $\beta$ に置き換えたものは、$M/B$ 露出点 $w$ と $\beta$ を結ぶ $M/B$ 交互道で、両端の辺は $M/B$ に属さない。これは $G/B$ の $M/B$ 増加道であり、$M/B$ は最大でない。
一般の場合は、ステム $P$（$M$ 露出点 $r$ から $b$ へ）で入れ替える。$P$ の長さが $0$ なら $b=r$ は露出点である。長さが正なら、$M':=M\triangle E(P)$ は大きさ $|M|$ のマッチングで、$r$ を飽和し $b$ を飽和しない（$P$ は偶数長で両端の辺は $M$ に属さない辺と $M$ に属する辺である）。$P$ と $B$ は辺を共有しないので $M'\cap E(B)=M\cap E(B)$ であり、$B$ は基点 $b$ の $M'$ 花である。$G/B$ では、$P$ の $b$ を $\beta$ に置き換えた道 $P/B$ は $M/B$ 露出点 $r$ から $\beta$ への偶数長の $M/B$ 交互道で、$M'/B=(M/B)\triangle E(P/B)$ は $|M/B|$ と同じ大きさである。$|M'|=|M|$、$|M'/B|=|M/B|$ なので、$M/B$ が最大なら $M'/B$ も最大で、前段により $M'$ も最大、したがって $M$ も最大である。$\square$

要点：外側の頂点の $M_i$ の辺は親への辺なので、外側の頂点から出る辺 $xy$ は $M_i$ に属さない。内側の頂点は辺を 2 本しかもたないので、2 本の根からの道の分かれ目は外側の頂点である。

停止：1 つの段では、成長は $F$ の外の頂点を 2 個減らし、縮約は $G_i$ の頂点を $2k\ge2$ 個減らす（$B_i$ の頂点はすべて $F$ にあり、$F$ の外の頂点の個数は変わらない）。よって成長は $n/2$ 回以下、縮約も $n/2$ 回以下で、段は増加か終了で終わる。増加は $|M|$ を $1$ 増やすので、段は $n/2+1$ 回以下である。
増加の正しさ：lem-eb-steps の 1 により $G_i$ の $M_i$ 増加道が得られ、lem-eb-shrink の 1 を $B_{i-1},\dots,B_0$ について順に当てると $G$ の $M$ 増加道になる（$B_j$ は $G_j$ の $M_j$ 花である）。入れ替えた $M\triangle E(Q)$ は大きさ $|M|+1$ のマッチングである（マッチング(グラフ理論) の定理「Berge の定理」の証明）。
出力の最大性：算法が終わるとき、段の最後の $G_t$、$M_t$、$F$ について、外側の頂点の隣接頂点はすべて内側の頂点である。内側の頂点の集合を $I$、外側の頂点の集合を $O$ とする。$G_t-I$ では外側の各頂点が孤立点なので、頂点数が奇数の成分は $|O|$ 個以上ある。$G_t$ の任意のマッチング $N$ について、そのような各成分は $N$ 露出点か $N$ で $I$ と組む頂点を含み、後者は $|I|$ 個以下なので、$N$ 露出点は $|O|-|I|$ 個以上ある（Tutteの定理 の定理「Tutte–Berge の公式」の前半と同じ議論）。一方、$M_t$ 露出点は根だけで、定義の後の等式によりちょうど $|O|-|I|$ 個である。よって $M_t$ は $G_t$ の最大マッチングである。lem-eb-steps の 2 により各 $B_j$ はステムをもつ $M_j$ 花なので、lem-eb-shrink の 2 を $j=t-1,\dots,0$ について順に当てると、$M_0=M$ は $G$ の最大マッチングである。$\square$

グラフを隣接リストで持つ。$G_i/B_i$ は、$B_i$ の頂点の名前を $\beta$ に付け替え、$\beta$ の自己ループと重複する辺を印を使って除けば $O(n+m)$ 時間で作れる。このとき $G_{i+1}$ の各辺 $y\beta$ に、それを生んだ $G_i$ の辺 $yv$ を 1 本記録しておく。
1 つの段を、縮約で区切られた部分に分ける。各部分ではグラフが変わらないので、外側の頂点を待ち行列に入れ、各外側の頂点の隣接リストを 1 回ずつ調べる。各辺は高々 2 回調べられ、成長は $O(1)$ 時間、増加の道と縮約の閉路は根への道を印を付けてたどれば $O(n)$ 時間で求まる。よって各部分は $O(n+m)$ 時間で、縮約の後は新しいグラフで外側の頂点をすべて調べ直す。部分は $n/2+1$ 個以下なので、増加道を見つけるまでに $O(n(n+m))$ 時間かかる。持ち上げは、各段階で記録した辺から $v$ を $O(1)$ で取り、道 $R$ を $O(n)$ 時間で挿入するので、$t\le n/2$ 段階で $O(n^2)$ 時間である。よって 1 段は $O(n(n+m))$ 時間で、段は $n/2+1$ 回以下なので、全体で $O(n^2(n+m))$ 時間である。$n\le2m$ なら $n+m\le3m$ である。$\square$