オイラーの一筆書き定理

 オイラーの一筆書き定理
　　　連結グラフが一筆書きできる必要十分条件は，奇点が０個または２個である．▮

前回は必要条件であることを示して、７つの橋問題を解決しました。
今回は十分条件であることを示します。これにより下図の８つの橋は２度以上通ることなく歩いて渡ることができます。

実際に何度か試してみれば渡れることは確認できます。ここで大切なのは実際にやらなくても可能だと判断できることです。

４つの島を点だと思えば、北島･下島は偶点で中島･横島は奇点なので中島か横島からスタートすれば８つの橋を渡ることができます。もしも中島と横島にもう１本橋が架けられたらどの島からスタートしても２度渡ることなく９つの橋を渡ることができます。

（ここから本題です）
まずは確認です。奇点はその点から出ている線の本数が奇数の点で、偶点はその点から出ている線の本数が偶数の点でした。次に連結グラフです。点と線だけの図形をグラフと呼び、そのグラフの任意の２点がそれらの線で結ばれているとき連結グラフと呼びます(※0)。例えば曇の天気記号◎は連結でないグラフです。このように線は曲線でも構いません。それに連結でないなら考えるまでもなく一筆書きはできませんね。

補助命題　どんなグラフも奇点は偶数個である．▮（証明は※1）
定理　連結グラフが一筆書きできる必要十分条件は，奇点が０個または２個である．▮

（十分性の証明の流れ）
連結グラフを一筆書きの要領でなぞり通過した線をどんどん消していき、すべての線が消えれば一筆書き可能といえます。その消し方を次に提示します。

すべて偶点のときは任意に点をとりそれをA、同時にA’とします。奇点が２つのときは一方をA、もう一方をA’とします。このときAは始点、A’は終点を意味します。

(1) Ａから出ている線が１本のときはその線を消し、その端点を新しいAとする。
(2) Ａから出ている線が２本以上のとき任意に１本の線を選ぶ。

　①その線を消してもグラフが連結ならそれを消し、その端点を新しいAとする。
　②その線を消してグラフが連結でなくなるなら別の線を消し、その端点を新しいAとする。これにより連結性は保たれる。(これは証明が必要で、このとき補助命題が使われます ※2)

この(1), (2)の操作によってどんどん線が消えていき次々新しいグラフが出来ますが、そのグラフは連結グラフで奇点は０個または２個です。こうして最後には２点Ａ, A’を結ぶ線が１本残るのでそれを(1)によって消し一筆書き完了です。▮

※緑の〇は１つのグラフを形成していることを意味しています。上の左下のようなグラフを考えてください。

【参考文献など】
前回の逆を示そうとすべて偶点であることが示せれば十分とみてあれこれ考えてみたのですがうまくいかず、蔵書で一筆書きの記述を読んだ記憶があるので探してみたら、難波 誠 著『幾何学12章』に書かれていました。世紀末2000年に出版された本で、読んだときに理解できなかったのを思い出しました。pp.81-86に記述されています。読んでは考え、読んでは考えし、理解できないので別証を考え、そして４度目に理解できたのでそれを書きました。上の(2)の証明からあとの理解がなかなかできなかったのです。別証を考えることで理解することができたのです。

話のついでに、記憶は定かではありませんが多湖 輝 著『頭の体操』シリーズ（光文社）に次のようなことが書かれていました：「ケーニヒスベルクの７つの橋の下を流れる川には必ず源流が存在するのでその源流まで歩いて行きその裏を回れば一筆書きができる（７つの橋問題は可能）」。実に柔軟な考えですね。▢

※０　連結は繋がっているということです。位相を知っている人には弧状連結と言った方がいいかと思いますが、グラフ理論ではこのような言葉遣いをするようです。グラフもそれに倣いました。

※１　ｍ個の点がｋ本の線で結ばれているとする．ｍ個の点はｓ個の奇点とｔ個の偶点に分けられる．これらの奇点，偶点から出ている線をすべて数えると 2k 本である．なぜなら，どの線も両端点で数えられているからである．したがって，
　　　(ｓ個の奇点から出ている線の本数)＋(ｔ個の偶点から出ている線の本数)＝2k
が成り立つ．そこで

　　　(ｓ個の奇点から出ている線の本数)＝2k－(ｔ個の偶点から出ている線の本数)
と変形したとき右辺は偶数なので左辺も偶数である．よってｓは偶数でなければならない.▮

※２　(2)-②：選んだ線の端点の一方はAであるからもう一方をBとする．この線ABを消すと連結でなくなるとする．
[1] すべて偶点のとき
線ABを消すと連結でなくなり，線を消した後の２点A, Bは奇点になる．このとき分断された２つのグラフのそれぞれには奇点A, Bが１個ずつしかない．これは補助命題に反する．したがってすべて偶点のときに線ABを消して連結でなくなることはない．
[2] 奇点が２個のとき
点A, A’が奇点である．線ABを消すと連結でなくなるとき，分断される２つのグラフを考えると点Aは偶点となるので，補助命題から点A’は点B側にあることになる．このとき点B側には奇点が０個か２個ある．奇点が０個となるのは点BとA’が一致しているときである．
さて点A側は点Aを除いてすべて偶点で線ABの他に任意に線ACを選べる．線ABを消さずに線ACを消すことでグラフの連結性は保たれる．このとき奇点は点C(改めてこれをAとする)と点A’の２点である．なお，線ACを消して連結でなくなることはない．もし連結でなくなったら再び補助命題に反するからである．▮