一筆書きの二色問題

よろしくお願いします。
小学生の時、始点と終点が一致する一筆書きは、必ず隣り合わずに２色で塗り分けられることを発見して驚きました。
証明はどうすればよいのでしょうか？
予感としては、途中から、－１の偶数乗は１、奇数乗はー１であることと同値になりそうな気がするのですが・・・

No.2 ベストアンサー 回答者： ありものがたり 回答日時： 2020/02/12 18:57

一筆書きで巡回する道に沿って

交互に色を塗ってけばいいんじゃないの？

この回答へのお礼

ありがとうございます。
なるほど。
道に沿って、始点から終点までの交点の数が偶数であることが示せたら、証明終わりですね！

お礼日時：2020/02/13 21:02

No.5 回答者： usa3usa 回答日時： 2020/02/14 09:02

>考えてみましたが、全然できませんでした。

私の実力不足。。。
その前に、私の書いた確認内容について正誤の応答するのが必要と思いますけど・・

No4＞その文章でそう解釈しろってのはいくらなんでも無理がある.
同感です。
No1さんへのお礼＞三角形は、外を白、内側を黒の２色で塗り分けられますが・・・Tacosanの意図とかみ合っていなかったらごめんなさい。
から推測して
No3＞「２色で塗り分ける」のは一筆書きの点ではなく、一筆書きの図形によって囲まれた面ですよね。
と助け船をだしたので、正誤の応答するのはエチケットだと思います

で本題

質問者さんは、
No4＞2. 従って双対を考えると全ての閉路が偶数本の辺を持つ
No4＞3. なので双対は二部グラフ
の２から３への証明はどうすればよいのでしょうか？
という質問と理解しています。

この理解であってますか？

この回答へのお礼

すみませんでした。正誤応答せず。
No.4さんのご回答は、まだ私は理解できていません。「２から３への証明」をすれば良いのかどうかもわかりません。
No.2さんのご回答は、数学素人の私にとっては大ヒントだと思うのですが。。。
ありがとうございます。

お礼日時：2020/02/14 16:32

No.4 回答者： Tacosan 回答日時： 2020/02/13 23:32

その文章でそう解釈しろってのはいくらなんでも無理がある.

「始点と終点が一致する一筆書き」が平面に書かれているとすればグラフ理論的にはさほど難しい問題ではなく
1. 「始点と終点が一致する一筆書き」では全ての頂点の次数が偶数である
2. 従って双対を考えると全ての閉路が偶数本の辺を持つ
3. なので双対は二部グラフ
4. もとに戻す
で終わり.

この回答へのお礼

言葉足らずですみませんでした。
グラフ理論は勉強したことがありませんが、それで証明になるわけですね？
ありがとうございます。

お礼日時：2020/02/14 16:23

No.3 回答者： usa3usa 回答日時： 2020/02/12 23:06

確認ですが、

「２色で塗り分ける」のは一筆書きの点ではなく、一筆書きの図形によって囲まれた面ですよね。

＞証明はどうすればよいのでしょうか？
一筆書きの図形ではなく、複数の閉多角形の辺の集合と考えて
　頂点数Nによる帰納法
や
　閉多角形Mによる帰納法
で証明、出来ませんか？

この回答へのお礼

ありがとうございます。
考えてみましたが、全然できませんでした。私の実力不足。。。

お礼日時：2020/02/13 21:02

No.1 回答者： Tacosan 回答日時： 2020/02/12 02:00

えぇっと....

三角形は?

この回答へのお礼

ありがとうございます。三角形は、外を白、内側を黒の２色で塗り分けられますが・・・Tacosanの意図とかみ合っていなかったらごめんなさい。

お礼日時：2020/02/12 15:50