ある辺を１つ選んで伸ばしていくことを考えます。

行き止まりがないので、いずれ通った頂点に戻ってくるはずです。（通った頂点に戻ってくる前に行き止まりがあるとすると、入次数が $1$ であるのに出次数が $0$ の頂点があることとなり矛盾します）

通った頂点に戻ってきたとき、サイクルができています。

サイクルを取り除いていったとき、「$0$ 辺ではないが、サイクルも存在しないグラフ」ができたと仮定します。

サイクルもオイラーグラフであることに留意すると、オイラーグラフからサイクルを取り除いたものは明らかにオイラーグラフです。よって、補題２よりサイクルが存在するはずなので矛盾します。

よって、必ず $0$ 辺になり、アルゴリズムは停止します。

そもそも、これは一般の $N$ 頂点では成立しません。（要反例）よって、$4$ 頂点の場合のみの証明を与えます。（また、グラフの足し引きを定義なしに用いていますが、辺集合に対する演算だと思ってください。あまり厳密にしなくても大意は理解できると思います）

補題３から、取り除く順番によって停止しなくなることはないため、単に解が悪化しないことを示せば十分です。解が悪化するとは、「そのサイクルを取り除かなければ、サイクル数が増えた」という状況を指します。そのような状況が起こり得ないことを示します。

このアルゴリズムにおいて $5$ 辺以上のサイクルは存在しません。なぜならば、同じ頂点を $2$ 回以上用いるサイクルは自明に極小ではないから、そのようなサイクルはすでに取り除かれているはずだからです。よって、以下で考えるサイクルはすべて極小なサイクルです。（また、ここから考えなければならないサイクルの種類数が $O(1)$ であるのでアルゴリズムが十分高速にまわることもわかります）

「あるサイクル $X$ 」を取り除いたときに、解が悪化すると仮定します。このとき、「あるサイクル $X$ に含まれる辺がすべておなじサイクル $Y$ に使われること」はありません。なぜなら、そのようなサイクル $Y$ は、サイクル $X$ と $Y - X$ に分解できるためです。

まず、 $1$ 辺のサイクルに関しては、明らかに上の議論から取り除いて良いです。（$1$ 辺しか無いので、必ず同じサイクルに使われます）

$2$ 辺のサイクル $X$ について考えます。$X$ にふくまれる $2$ 辺が異なる $2$ つのサイクル $Y, Z$ に使われたとしても、その $2$ つのサイクルを組み替えれば $X$ と $Y+Z-X$ の $2$ つのサイクルにできるため、$2$ 辺も取り除いてよいです。（これは一般のグラフで成り立ちます）

$3$ 辺のサイクル $X$ について考えます。（このとき、既に $2$ 辺以下のサイクルはすべて取り除かれていることに注意します）上の $2$ 辺の議論を考えれば、$3$ 辺が $2$ つのサイクルに分かれる場合は取り除いて良いこととなります。

よって、$3$ 辺はすべて異なる（極小な）サイクル $Y,Z,W$に含まれるとして良いです。しかし、そのような異なる $3$ つのサイクルであって、$Y + Z + W$ が「 $2$ 辺以下のサイクルを含まない」ものは存在しません。それを示します。

まず、$X$ に含まれない頂点を $u$ と置きます。この頂点は $Y,Z,W$ のいずれにも含まれます。なぜならば、そうでないときは（そのサイクル自体が） $2$ 辺のサイクルを含むか、$X$ と一致するためです。　$Y+Z+W$ において、 $u$ に向かう辺も $u$ から伸びる辺も $3$ 本ありますが、$2$ 辺のサイクルが無いことを考えると、向かう辺か伸びる辺のどちらかは $X,Y,Z$ で一致します。（鳩の巣原理を考えればわかります）すると、ある頂点において、入次数または出次数が $4$ となり、これはあるサイクルが $2$ 回以上おなじ頂点を用いていることとなります。しかし、これは極小であることに矛盾します。

$4$ 辺のサイクルは明らかに取り除いてよいです（ $4$ 辺が最大より、解の悪化のしようがありません）

よって、サイクルの数が悪化することはないために、サイクルの数は最大化されています。

まず、明らかに操作回数は「$s - 1$ 」です。

$(i_1, i_2)$ を操作したとき、元のグラフを考えると、$i_1$ と $i_2$ の始点が入れかわります。$i_1$ については $A_{i_1} = B_{i_1}$ となります。そして、$i_2$ の始点は $i_s$ の終点と一致します。

そのため、新しいサイクルとして $i_2, i_3, \dots ,i_s$ というサイクルができます。これを繰り返すことで、この操作列が得られます。

そのような操作列が存在すると仮定します。

このとき、操作列を辺として解釈したグラフを考えます。集合 $S$ に存在する要素は $s$ 個であるのに対して、辺の本数（ $=$ 操作回数）は高々 $s-2$ ですから、少なくとも $2$ つ以上の連結成分にわかれます。

連結成分に含まれる index のみに着目すると、これは元問題とおなじ状況です。よって、連結成分は $1$ つ以上のサイクルに分解できることはずなので、元のサイクルは $2$ つ以上のサイクルに分解されます。よって「極小のサイクル」であることに矛盾します。

補題７と同様に、操作列を辺として解釈したグラフについて、連結成分ごとに考えます。まず、その連結成分の大きさを $s$ とすれば、明らかに操作が $s-1$ 回以上含まれます。

その連結成分は同様に $1$ つ以上の極小なサイクル（ $c$ 個とします）に分解できます。そのサイクルに対して「サイクル操作列」を行うと、操作回数は $s -c$ となります。これは、 $s-1$ 以下なので示されました。