7-1 Eulerグラフとde Bruijn列

closed trailが頂点 $v$ を通るたび、一本の辺で入り、別の一本で出ます。始点でも、最後に入る辺と最初に出る辺が対になります。従ってtrailが $v$ に接続して使う辺数は偶数です。元の偶数次数から偶数本を引くので、残余次数も偶数です。□

未使用辺 $xy$ を一本取ります。$C$ 上の頂点 $c$ から $x$ へのpath
$$ c=v_0,v_1,\ldots,v_r=x $$
があります。$x$ が既に $C$ 上なら、$xy$ が求める辺です。そうでない場合、path上で $C$ の頂点から $C$ 外へ初めて出る辺を $v_iv_{i+1}$ とします。
もしこの辺が使用済みなら、それは $C$ の辺ですから両端 $v_i,v_{i+1}$ が $C$ 上に現れるはずで、$v_{i+1}$ が $C$ 外であることに反します。従って $v_iv_{i+1}$ は未使用で、$C$ 上の $v_i$ に接続します。□

最初に $s$ から延長不能になるまで未使用辺をたどります。全次数は偶数なので、偶数次数グラフのmaximal trailの議論により、このtrailは $s$ へ戻ります。
一つのclosed trailを取り除いた後の残余次数は補題 [25-lem-residual-even-degree] により偶数です。従って、手順3で選んだ $v$ から残余グラフ内を延長不能になるまで進むtrailも $v$ へ戻り、closed trail $D$ になります。
貼り合わせ補題により、辺を共有しない $C,D$ を $v$ で挿入したものは、両方の辺を一度ずつ使うclosed trailです。未使用辺が残れば、補題 [25-lem-unused-edge-meets-current-trail] により次の再開点があります。
各反復で少なくとも一本の未使用辺を使用済みにします。辺数 $m=|E(G)|$ は有限なので、反復は高々 $m$ 回で止まります。停止条件は未使用辺がないことですから、最後のclosed trailは全辺をちょうど一度ずつ使うEuler circuitです。□

stack内では同じ頂点が何度も現れ得るので、頂点名ではなく出現位置を区別します。最初の $s$ 以外の各出現位置には、それをpushした固有の辺を「入辺」として対応させます。pushと使用辺は一対一なので、入辺は相異なります。
まず、算法が初めてpopを行うまでを見ます。それまでのpush列は、未使用辺を延長不能になるまでたどったtrailです。偶数次数の議論により、その終点は開始頂点 $s$ です。従ってstackには一つのclosed trailの頂点列が積まれています。
ここからpopを続けると、このclosed trailは逆順に $L$ へ移ります。途中の出現位置 $v$ で未使用辺が見つかれば、popはそこで止まり、$v$ から新たなpush列が始まります。残余次数は補題 [25-lem-residual-even-degree] により偶数なので、この新しいpush列も $v$ へ戻るclosed trailになります。そのtrailの頂点列が先に逆順で $L$ へ移り、その後に元のclosed trailのpopが再開します。従って、$L$ を逆順にした列では、新しいclosed trailが元の列の $v$ の位置へ挿入されています。
未使用辺がある限り同じことを繰り返すので、stack版が作る逆順列は、貼り合わせ版で相異なる辺からなるclosed trailを順次挿入した列と一致します。各挿入の前後で隣接頂点は対応するtrailの辺で結ばれ、同じ使用辺を二度挿入しません。また各push辺は、それを含むclosed trailの隣接箇所として必ず一度現れます。従って主張が成り立ちます。□

補題 [25-lem-stack-edge-correspondence] により、逆順の $L$ は、stack版が使用した辺をそれぞれ一度ずつ並べるclosed trailです。もし算法終了時に未使用辺が残っていれば、このclosed trail上の頂点に未使用辺が接続することが補題 [25-lem-unused-edge-meets-current-trail] から従います。しかしその頂点の最後の出現位置をpopするときには、接続する未使用辺があるため else へ進めず、先にその辺を使ってpushしなければなりません。これは未使用のまま終了したことに反します。従って全辺が使用され、出力はEuler circuitです。
計算量を数えます。無向辺は隣接リストに両端から一回ずつ、合計 $2|E|$ 個の項目として現れます。各頂点の走査位置は後ろへしか進まないため、全隣接項目を調べる回数は $O(|E|)$ です。各辺は一度だけ使用済みにされ、そのときpushが一回起こります。各pushされた頂点は一度だけpopされます。孤立頂点を含む入力表の準備に $O(|V|)$、隣接項目とstack・出力列に $O(|V|+|E|)$ 空間を使います。従って主張の計算量になります。□

補助辺を加えると $s,t$ の次数は偶数になり、他の次数は変わりません。従って増補グラフはEuler circuit $C$ をもちます。$C$ を補助辺 $t\to s$ の直後から書けば
$$ s,\ldots,t,s $$
となります。最後の補助辺を削れば、元の全辺を一度ずつ使う $s$ から $t$ へのtrailが残ります。□

強連結成分を一頂点へ縮めて得る縮約有向グラフ $Q$ を考えます。異なる強連結成分間のarcだけを残せば、$Q$ は有向cycleをもちません。実際、成分間に有向cycleがあれば、そのcycle上の成分同士は相互に到達でき、一つの強連結成分でなければなりません。
$Q$ が二頂点以上なら、有限acyclic digraphなので入次数0の頂点、すなわち外部からarcが入らない強連結成分 $S$ があります。元の有向グラフで $S$ の頂点について
$$ \sum_{v\in S}\bigl(d^+(v)-d^-(v)\bigr)=0 $$
です。$S$ 内部の各arcは和へ $+1$ と $-1$ を一つずつ寄与して相殺します。残る値は「$S$ から外へ出るarc数」から「外から $S$ へ入るarc数」を引いたものです。後者は0なので、前者も0です。
従って $S$ と他の成分を結ぶarcはありません。しかし基礎無向グラフは正次数頂点上で連結なので、これは矛盾です。ゆえに強連結成分は一つだけです。□

必要性を示します。有向Euler circuit上では、頂点 $v$ へ入るたびに次のarcで出ます。始点でも最後の入arcと最初の出arcが対になるため、全arcを数えると $d^+(v)=d^-(v)$ です。また、arcをもつ任意の頂点はcircuit上に現れるので、向きを忘れれば同じ連結成分に属します。
十分性を示します。正次数頂点 $s$ から未使用arcを向きに従って、延長不能になるまでたどります。終点を $t$ とします。もし $t\ne s$ なら、使用したtrailでは $t$ へ入った本数が $t$ から出た本数より1多いです。一方、全体では $d^-(t)=d^+(t)$ なので、未使用出arc数は未使用入arc数より1多く、特に未使用出arcがあります。これは延長不能に反します。従ってtrailは $s$ へ戻ります。
このclosed trailのarcを除くと、各頂点で除いた入arc数と出arc数が等しいため、残余有向グラフもbalanceしています。未使用arcが残るなら、基礎無向グラフの連結性を用いた補題 [25-lem-unused-edge-meets-current-trail] と同じpathの議論により、現在のclosed trail上の頂点 $v$ に未使用arcが接続します。そのarcが $v$ から出るなら直ちに再開できます。そのarcが $v$ へ入るものなら、残余で $d^+(v)=d^-(v)$ なので未使用出arcも少なくとも一本あります。
$v$ から同じ操作を行えば新しい有向closed trailが得られ、元のtrailへ挿入できます。各反復で使用arcが増えるので有限回で全arcを使い切ります。従って有向Euler circuitを得ます。□

必要性は、trailの中間頂点では入るarcと出るarcが対になり、始点では出るarcが一本、終点では入るarcが一本余ることから従います。全arcが同じtrail上にあるため、弱連結性も必要です。
逆に条件が成り立つとします。補助arc $(t,s)$ を一本加えると、$s$ の入次数と $t$ の出次数がそれぞれ1増え、全頂点で入次数と出次数が等しくなります。弱連結性は保たれるので、前定理により増補グラフは有向Euler circuitをもちます。そのcircuitを補助arcの直後で切り、補助arcを削れば、$s$ から $t$ への有向Euler trailになります。□

長さ $k-1$ の語の各位置には $q$ 通りの選択があるので頂点数は $q^{k-1}$、長さ $k$ の語の個数は $q^k$ なのでarc数は $q^k$ です。
頂点 $u=a_1\cdots a_{k-1}$ から出るarcは、末尾に任意の文字 $b\in A$ を加えた語 $a_1\cdots a_{k-1}b$ に対応するので $q$ 本です。入るarcは、先頭に任意の $b\in A$ を加えた語 $ba_1\cdots a_{k-1}$ に対応するので、やはり $q$ 本です。
任意の二頂点
$$ u=a_1\cdots a_{k-1},\qquad v=b_1\cdots b_{k-1} $$
を取ります。$u$ から順に $b_1,b_2,\ldots,b_{k-1}$ を末尾へ付け加えるarcをたどると、左端の文字が一つずつ落ち、$k-1$ 歩後に $v$ へ到達します。従って任意の $u$ から任意の $v$ への有向pathがあり、強連結です。□

$k=1$ なら、$q$ 個の文字を一度ずつ円周上に並べればよいです。以下 $k\ge2$ とします。
補題 [25-lem-de-bruijn-balanced-connected] により、$B(q,k-1)$ は全頂点で入次数と出次数が等しく、正次数頂点上で連結です。有向Euler circuitの定理から、$q^k$ 本のarcを一度ずつ通るcircuitがあります。
circuitの開始頂点を
$$ a_1a_2\cdots a_{k-1} $$
とし、順に通るarcの終点へ新たに入った末尾文字を
$$ c_1,c_2,\ldots,c_{q^k} $$
とします。直線上では
$$ a_1a_2\cdots a_{k-1}c_1c_2\cdots c_{q^k} $$
と書けます。
$i$ 番目のarcを通る直前の頂点は、その時点の末尾 $k-1$ 文字であり、そこへ $c_i$ を付けた長さ $k$ の語が、そのarcのlabelです。Euler circuitは各arcをちょうど一度通り、arcは $A^k$ の語と一対一に対応します。従って連続する長さ $k$ の窓には、各語がちょうど一度ずつ現れます。
circuitは開始頂点へ戻るので、最後の $k-1$ 文字は最初の $a_1\cdots a_{k-1}$ と一致します。この重複部分を除き、円周上に $q^k$ 文字を置けばde Bruijn列になります。□

最初のtrailが使っていない辺は $14,45,51$ です。現在のtrail上の頂点1に未使用辺が接続するので、1から
$$ 1,4,5,1 $$
というclosed trailを作れます。最初のtrailの最後の1の位置へ挿入すれば
$$ 1,2,3,1,4,5,1 $$
です。六辺がすべて一度ずつ現れるのでEuler circuitです。□

次数は1と3で3、2と4で2です。奇数次数頂点1,3の間に、元の辺13とは番号で区別した補助辺 $e_*$ を加えます。増補グラフのEuler circuitとして
$$ 1,2,3,4,1,3,1 $$
を取れます。最後の $3,1$ を補助辺 $e_*$ と選び、そこを切ると
$$ 1,2,3,4,1,3 $$
が残ります。これは元の五辺を一度ずつ使う1から3へのEuler trailです。□

次数は
$$ \begin{array}{c|cccc} v&a&b&c&d\\ \hline d^+(v)&2&1&1&1\\ d^-(v)&1&1&2&1 \end{array} $$
です。$a$ では出次数が1多く、$c$ では入次数が1多く、他はbalanceしています。基礎無向グラフは連結なので、$a$ から $c$ への有向Euler trailがあります。例えば
$$ a\to b\to c\to a\to d\to c $$
です。始終点が異なるのでEuler circuitはありません。□

頂点は $00,01,10,11$、arcは長さ3の全二進語です。例えば
$$ 00\xrightarrow{001}01 \xrightarrow{011}11 \xrightarrow{111}11 \xrightarrow{110}10 \xrightarrow{101}01 \xrightarrow{010}10 \xrightarrow{100}00 \xrightarrow{000}00 $$
は全arcを一度ずつ使います。開始頂点00と、順に付け加わる文字 $1,1,1,0,1,0,0,0$ を並べると
$$ 0011101000 $$
です。末尾00を重複分として除くと、巡回列
$$ 00111010 $$
を得ます。その巡回3文字窓は
$$ 001,011,111,110,101,010,100,000 $$
で、全二進3語を一度ずつ含みます。□

任意の目標頂点 $b_1\cdots b_{k-1}$ に対し、現在の頂点の末尾へ $b_1,b_2,\ldots,b_{k-1}$ を順に追加すれば、$k-1$ 歩後には目標頂点になります。従って距離は高々 $k-1$ です。
$00\cdots0$ から一歩進むと、元の0を左から一つ捨て、新しい文字を右へ一つ加えます。$r$ 歩後にも、$r< k-1$ なら元の0が少なくとも一つ残っています。従って全成分が1の頂点には到達できません。ゆえにこの二頂点間の距離は少なくとも $k-1$ で、実際にちょうど $k-1$ です。□

長さ $N$ の巡回列には、開始位置を一つ指定するごとに長さ $k$ の巡回部分語が一つあり、開始位置は $N$ 箇所です。従って異なる長さ $k$ 語は高々 $N$ 個しか現れません。全 $q^k$ 語を含むには
$$ N\ge q^k $$
が必要です。
de Bruijn列の長さは定義により $q^k$ で、その $q^k$ 個の窓がすべて異なる語です。従って下界を等号で達成し、可能な巡回列のうち最短です。□