一筆書問題

　なんとなく誰もが一度はやったことがあるんではなかろうか、とか思っている代物。同じ場所をなぞらずに（交差するのはあり）、その図形を書ききることができるかという問題。この問題で有名なのは、ケーニヒスベルクの橋というドイツだかにある何個かの橋を、同じ橋を２回通過することなく、全部の橋を回れるかという問題だが、オイラーによって解決された。
　　　　

　たとえば、左上の図形はどの頂点からスタートしても一筆書できる。右上はどこからでもというわけではないが、底辺の両端のどちらからスタートすれば一筆書できる。下列はどうあがいても、一筆書できない（ちなみに右下がケーニヒスベルクの橋と呼ばれる図形である）。ではこの理由はなんなのだろうか？

　答えは各頂点に集まる辺の数にある。一筆書なのだから、各頂点には入って出て行く２本の辺が集まっていくはずである。つまり、各頂点には偶数本の辺が集まっていることがひとつ条件である。偶数本の辺が集まる頂点を偶点、奇数本を奇点と呼ぶことにするとすべての頂点が偶点である。しかし、奇点があっても良い場合がある。つまり、入るだけ、出るだけという特殊な頂点がある。すなわちスタートとゴールの点である。これが一致する場合が先に言ったすべて頂点が偶点という場合である。よって、２つだけ奇点があるという状況でも良い。

　○　すべての頂点が偶点、あるいは２つだけ奇点がある場合は一筆書可能。

　○　２つ以上奇点がある場合は一筆書不可能。（奇点が奇数個あることはありえない）

　上記の図形で確かめてみれば、この意味が納得できると思う。