一筆書きの定理の理由

このエントリーをはてなブックマークに追加
8Quserman ◆KeLXNma5KE
>>1
残念だけど、連結でないグラフは一筆書き不可能である。
以下、グラフは連結で、頂点と綾が有限個のものに限ろう。
まず、綾一つにつき、頂点が2個対応するので、奇頂点の数は偶数個である。
奇頂点の数が2個のとき、奇頂点に関しての筆の出入りの総数は奇数なので、
奇頂点が一筆書きの始点または終点にならなくてはいけない。
以下、グラフは奇頂点が2個または0個で、奇頂点が2個の場合は奇頂点から書き始めるものとする。
奇頂点が0個のとき、綾の途中から書き始めるときは、そこに頂点を1個つけたグラフの一筆書きと同じなので、
一筆書きは頂点から始めるものとする。
(簡単のため、線が途中で交差してもよいと仮定する。)
まず、始点から、ある頂点に向かって線を引く。
このとき、通った綾を消したグラフを考えると、それは、
今いる頂点から始めて、このグラフの一筆書きをせよという問題になる。
行き着いた先の頂点が1個の綾のみの端点になるときは、
初めのグラフが一つの綾と、2つの頂点からなるものである時のみである。
(奇頂点は高々2つだから。)
だから、綾が2つ以上あるグラフのときは、始めに綾を一つ書いたとき、
必ず2つ以上の綾の共通頂点に筆が行き着く。
そして、グラフが有限で連結なので、綾を一つずつ消して、新しい一筆書きの問題を作るという操作は、
綾が一つになるまで続けられる。よって、奇頂点が2個または0個のグラフは一筆書き可能である。
ちなみに、奇頂点が2個より多いとき一筆書きができないことは明らかだろう。
線を交差させてはいけないという条件が付いたときも一筆書きの可能性は変わらないらしいが、
誰か、このことを証明してくれ。