追加順が未定の辺の中で最初に追加するとして良い事

最終的なグラフにおいてどのようなサイクルにも含まれない辺は、前に追加した辺から制約を受ける事はあっても、後に追加する辺に制約を課す事はない。
また、最初に追加したとしても、その辺が制約を違反する事はない。
よって、条件を満たす辺の追加順が存在するならば、そのような辺は最初にまとめて追加するとした新たな追加順も条件を満たす。

以降、初めから存在しなかったとして考えて良い事

かつ、このように最初に追加した辺はサイクルの成立に関わらないので、後に追加する辺に制約を課す事はない。

辺 \(e\) を最後に追加する事によって、制約が違反されない事

辺 \(e\) が追加できない状況を考える。

それは 辺 \(e\) を取り除いたグラフにおいて、 \(u\) 或いは \(v\) が既にサイクルに含まれている状況である。

しかし、辺 \(e\) を取り除いたグラフにおいて、 \(u\) , 及び \(v\) の次数は高々 \(1\) であるから、 \(u\) 或いは \(v\)　が既にサイクルに含まれていることはあり得ない。

よって、 辺 \(e\) の追加によって制約が違反される事はない。

用語の設定

辺の集合に対して、最後に追加する辺を任意に取り、辺 \(e' = (u', v')\) と置く。及び、辺 \(e'\) だけを取り除いたグラフを \(g\) と置く。

\(u', v'\)の対称性及びグラフに対する仮定より、グラフ \(g\) において、 \(v'\) の次数 \(\ge 2\) として良い。

ここで、 \(g\) において \(v'\)に直接繋がっている頂点から任意に \(2\) 頂点選び、それぞれ \(a, b\) と置く。

背理法による証明

\(v'\) が \(g\) においてサイクルに含まれていないと仮定する。

辺 \(e'\) を追加したグラフにおいて、 辺 \((a, v')\) がサイクルに含まれる辺であることから、 \(g\) に 辺 \(e'\) を追加したグラフ上には辺 \((a, v')\) を用いない \(v'\) —> \(a\) の頂点素・辺素なパスが存在する。

しかし、辺 \(e'\) を追加する直前に \(v'\) がサイクルに含まれないことにより、辺 \(e'\) を追加する前段階でははそのような \(v'\) —> \(a\) のパスは存在しない。

よって、最終的なグラフにおけるそのような \(v'\) —> \(a\) のパスは 辺 \(e'\) を通る。

つまり、グラフ \(g\) において \(u'\) —> \(a\) の頂点・辺素なパスであって頂点 \(v'\) を含まないものが既に存在する。

同様に、 \(u'\) —> \(b\) の頂点・辺素かつ頂点 \(v'\) を含まないパスも存在する。

それを合体させる事で、 \(a\) —> \(u'\) —> \(b\) のパスをグラフ \(g\) 上に得る。

及び、 \(a\) —> \(u'\) —> \(b\) のパスにおいて、 \(2\) 回以上登場する辺や頂点が存在する限りその間を消すことで、最終的に \(a\) —> \(b\) の頂点・辺素かつ頂点 \(v'\) を含まないパスを得られる。

そして、このパスを用いて \(v'\) -> \(a\) —> \(b\) -> \(v'\) のサイクルが \(g\) 上に得られる。 つまり、 \(v'\) が \(g\) 上サイクルに含まれていないという仮定は矛盾である。