☆四色問題の簡単な証明その３☆

**帰納と類比** · 2011/02/26(土) 23:20:22.98

過去ログ
http://unkar.org/r/math/1266094084
四色問題の証明は簡単にできる。過去ログのNO.29を参照してください。
ブログ作ったのでコメントしてください。
http://blog.livedoor.jp/ys7420/archives/51665060.html
この板のこのスレでも、どちらでもいいので分からないところを聞いてください。
証明は過去のものと同じです。清書すると費用が掛かるので改善しませんでした。
申し訳ない。
contract＝接合と考えていいですが、接合は５色以上必要になる可能性を持っています。
過去ログで議論したことはなるべく出さないでください。
ブログを立ち上げたのは、image（証明３ページ）が消えてもいいためです。
では反論でも感想でもいいですので、気兼ねなく尋ねてください。
よろしくお願い致します。

**１３２人目の素数さん** · 2011/02/26(土) 23:30:16.68

幼稚園の子供に塗り絵をさせて４色で塗れたら証明完了

**１３２人目の素数さん** · 2011/03/02(水) 18:41:52.45

> 過去ログで議論したことはなるべく出さないでください。

お前が言うな

**帰納と類比** · 2011/03/02(水) 21:50:17.12

>>1
幼稚園の子供に「蜂の巣状の６辺国」を塗らせてみたらどうでしょう。
子供だからある法則に気が付かなければかなり時間が掛かるでしょう。
これで子供は証明完了？

>>2
過去ログに関係なく自由に議論しましょう。（訂正）
過去ログは参考までに見といてください。

**∴猫は多重精神病** ◆MuKUnGPXAY · 2011/03/02(水) 22:47:45.58

猫

>724 名前：１３２人目の素数さん：2011/03/02(水) 22:28:23.32
> >>KuzuNOSeihanzaish
> 数学に捨てられ「た」性犯罪者でしょうか？
> 社会の屑の印象をどうしても受けます。
>

**帰納と類比** · 2011/03/14(月) 20:03:05.91

過去ログいちいち見るのめんどくさいんで、証明は下記UPロダに載せました。

http://dl7.getuploader.com/g/4%7Cpl/116/pl_116.jpg
http://dl7.getuploader.com/g/4%7Cpl/117/pl_117.jpg
http://dl7.getuploader.com/g/4%7Cpl/118/pl_118.jpg

上記証明を見て分からないところを質問してください。感想・反論・理解でもいいです。

接合とはグラフにおいて、色拘束された点と異なる色拘束された点を合わせて１点にすることで
５色以上の色になる可能性を持った点の重なりを言う。

字が汚くて申し訳ない。ささいな質問でも回答します。ぜひ読んでみてください。

**１３２人目の素数さん** · 2011/03/14(月) 20:07:44.89

Docode Error

**帰納と類比** · 2011/03/14(月) 20:53:37.53

>>7
「Docode Error」

はどうゆう意味ですか？
分からないので簡単に説明して頂けませんか。

**帰納と類比** · 2011/03/14(月) 20:57:26.78

<<7　Docode Error はどうゆう意味ですか？

**１３２人目の素数さん** · 2011/03/14(月) 21:04:01.91

Decode Error のスペルミスなんだろうが…
スレ主は何故粘着してるんだろうか

**１３２人目の素数さん** · 2011/03/15(火) 05:56:14.22

稀に見る糞スレ

**帰納と類比** · 2011/03/18(金) 22:58:41.26

>>10
確かにブログは　Decode　Errorです。うＰロダを参照してください。
>>11
稀に見る糞スレではありません。
ダイヤモンドの原石の様な証明です。
大学の数学科の助手以上の才能がないと理解出来ないかもしれません。
この板の住人には、四色問題を手がけた人いませんか。
居られるならば理解出来るでしょう。そうゆう人に出会いたいものだ。

**１３２人目の素数さん** · 2011/03/19(土) 07:48:19.84

5枝点が可約だという結論を導いていることだけでも嘘ってわかるじゃん。

**１３２人目の素数さん** · 2011/03/19(土) 15:16:20.53

>>12
頭悪いな

**帰納と類比** · 2011/03/19(土) 16:17:51.89

>>13
5集点が可約であると証明しました。5集点が可約ではないとゆう証明はあるのでしょうか。
あったら教えてください。ソースまたは著作物を教えてください。
>>14
「頭悪いな」ということは当たらないと思います。数学には自信があります。
大学のときの成績はtop10に入るほど頭は良かったです。現在は老化しており、
頭の良さは高校生並みです。1976年夏に四色問題に出会ってから34年経ってますから。
どんなふうに頭悪いのかな？

**１３２人目の素数さん** · 2011/03/19(土) 17:08:04.23

可約では無いだろうという予想は知ってるが、俺も証明されたとは知らないから、証明があったらマジ知りたい。おせーて。

**１３２人目の素数さん** · 2011/03/19(土) 17:35:48.07

>>13 はD可約性、C可約性と、ただの可約性を混同してるんじゃないか？

**１３２人目の素数さん** · 2011/03/19(土) 17:37:50.30

>>13
こんな所に書き込んでいる時点でｗ

**帰納と類比** · 2011/03/19(土) 17:52:30.60

>>18
正式に数学論文として大学から出す手段がないので、こんな所に書き込んでます。
本当は英文でハーバード大学から出したいと思ってますが、つてもなく英語も苦手だから
出せません。誰か英文で論文出してくれないかな。証明が正しいと思ったら。

**１３２人目の素数さん** · 2011/03/19(土) 19:35:57.40

誰のためでもなく、自分のために見てみるよ。
とりあえず、証明が見れない事を何とかしろ。

再UPでもしてくれ。

**１３２人目の素数さん** · 2011/03/19(土) 19:37:42.65

あ、ブログの方にあるのね。理解しづらい所は後で質問するからよろしく。

**１３２人目の素数さん** · 2011/03/19(土) 20:33:53.00

先生！>>6では、「接合」の意味がわかりません！
もっと詳しく教えてください。

簡単のために、4色の色を①②③④とします。
P0を除いて4色で配色した時、

Case I )
A①, B②, C①, D③, E④
となった場合、具体的にどのような操作をすることを言うのでしょうか？

Case II)
A①, B②, C①, D②, E③
となった場合、具体的にどのような操作をすることを言うのでしょうか？

**帰納と類比** · 2011/03/19(土) 22:48:34.87

>>22
CaseⅠ）
Ｂ②とＤ③を結合してＢ⑤とする。
Ｂ②とＥ④を結合してＢ⑤とする。
CaseⅡ）
①②③の３色なので接合する必要はない。P0を戻して④とすると４色で配色できる。
Ａ①とＣ①を結合してＡ①とする。
Ｂ②とＤ②を結合してＢ②とする。

接合はどの点でも色拘束を持って結合することを言う。
隣り合う接触した点と点は接合とは言わない。
接触しない点と点を色拘束を持ったまま結合（重ねる）することを接合と言う。

この説明で分かりますか。

**１３２人目の素数さん** · 2011/03/19(土) 23:31:37.14

>>23
Case II ) については、確かに考えなくていいですね。
失礼しました。

で、Case I ) についてですが、
B⑤とする。ということは、（一時的にでも）５色目を使うってことでしょうか？

あと一つ。
B②とD③を結合して、証明の２枚目の、P2みたいにする、
と言う理解でよろしいですか？

**１３２人目の素数さん** · 2011/03/19(土) 23:42:27.23

あ、原文でうは、４色をA,B,C,Dで表しているのですね。
混乱させてしまっては悪いので、記号を証明の原文に合わせて、再度質問しなおします。
(>>22,24 は無視して下さい）
―――――――――――――――――――
P0を除いた、庁点数が N-1 のグラフを４色で塗り分けた時、
(P1, P2, P3, P4, P5）の色が、（A, B, A, C, D）だった場合、接合とは、
①具体的に、P1～P5 を、２枚目のP1～P4にどう対応させるのですか？
②接合後の、（P1, P2, P3, P4）の色を教えてください。

以上、２点お願いします。

**帰納と類比** · 2011/03/20(日) 00:00:51.71

>>24
>B⑤とする。ということは、（一時的にでも）５色目を使うってことでしょうか？
そうゆうことです。色拘束があるため５色目を使わなければならないのです。

>B②とD③を結合して、証明の２枚目の、P2みたいにする
接合の場合、色拘束があるので、P2の様にはいきません。
あくまでもＢ⑤となります。ただし、Ｎ－２点のグラフは四色で塗れるので
Ｂ⑤は仮定に矛盾します。よってＢＤチェーンかＢＥチェーンのいずれか一方は切れてることになります。

**１３２人目の素数さん** · 2011/03/20(日) 00:23:05.26

>>26
えーと、まず、接合の理解から。
――――――――――――――――
>>25で言えば、
接合前の状態が（P1,P2,P3,P4,P5）：(A, B, A, C, D)だった場合、

①(P1, P2, P3, P4, P5) ⇒接合⇒(P1, P2, P3, P4, P2)

②接合後の(P1, P2, P3, P4）：（A, E, A, C）

という理解でよろしいでしょうか。

**帰納と類比** · 2011/03/20(日) 00:42:34.59

>>25
>(P1, P2, P3, P4, P5）の色が、（A, B, A, C, D）だった場合、接合とは、
①具体的に、P1～P5 を、２枚目のP1～P4にどう対応させるのですか？
（Ｐ５、Ｐ１、Ｐ２、Ｐ３、Ｐ４）の色が（Ａ、Ｂ、Ａ、Ｃ、Ｄ）と置き換えればいい。
>②接合後の、（P1, P2, P3, P4）の色を教えてください。
　（P1, P2, P3, P4）は（Ａ，Ｅ，Ａ，Ｃ）となります。（ＢＤチェーンが繋がってる場合）
　この場合、５色目のＥが必要になります。Ｎ－１点以下は４配色可能という仮定と矛盾しますが。

**１３２人目の素数さん** · 2011/03/20(日) 00:49:59.29

>>28
えーと、多分接合については理解できました。

ただ、一つ疑問点が出てきました。
接合を行うことで、５色目を使うことが必要になる（こともある）のですが、
この「５色目が必要」ということは、別に４配色可能であることと矛盾はしません。

接合するときは、
接合する２頂点の色以外の頂点の色は変えないこと…①を前提としております。
（>>27で言えば、P2とP5を、色Eにしただけで、他の全頂点の色は変えない事を前提としている。）

従って、上手く色を付け直せば、４色で塗り分けることが可能だとしても、
「①の前提では、５色必要になる」と言うことはありえます。

これについては、どのようにお考えなのでしょうか。

**帰納と類比** · 2011/03/20(日) 01:24:41.04

>>29
>従って、上手く色を付け直せば、４色で塗り分けることが可能だとしても、
「①の前提では、５色必要になる」と言うことはありえます。

チェーンの拘束があれば、５色必要になり、矛盾を生じる。
うまく色を付け直せば、チェーンは切れて、５点（P1，P2，P3，P4，P5）はＥを除く３配色可能となる。
ＢＣチェーンとＢＤチェーンが両方繋がっている場合しか存在しないと矛盾を生じる。

**１３２人目の素数さん** · 2011/03/20(日) 01:32:33.61

>>30
いえ、だから、
「特定の条件下では５色以上必要な事がある」ことは、
「４配色可能である」という仮定に矛盾しません。

例えば、証明の１ページにある、５つの頂点のグラフだけを考えてみます。
（配置とかではなくて、単に５つの頂点のグラフです。）

この時、何の制約もなければ、４配色可能なグラフであることは明らかです。

ただし、「P1をA, P2をB, P3をC, P4をD　とする」というような制約がある場合、
５色目が必要な事は明らかです。

ある特定の条件では５色以上必要なグラフでも、
全ての頂点の色を付け直して、上手く配色しなおすことで４色塗り分け可能であれば、
そのグラフは４配色可能であります。

言っていることは伝わっているでしょうか？

**帰納と類比** · 2011/03/20(日) 02:00:12.18

>>31
５色必要なグラフが１つでもあれば、４配色可能に矛盾します。
>全ての頂点の色を付け直して、上手く配色しなおすことで４色塗り分け可能であれば、
　そのグラフは４配色可能であります。
うまく配色し直しても、ＢＣチェーンとＢＤチェーンの両方が切れないと反例が生じます。
その事が矛盾になります。
ここの部分の考え方が、異なるようですね。

**１３２人目の素数さん** · 2011/03/20(日) 02:14:00.68

>>32
考え方の問題じゃない気が・・・

まぁ、貴方はあなたの信じる証明を
論文でもなんでもして、お出しになってはいかがでしょうか。

一応、あなたの証明の間違いだと思われる部分を、ハッキリと書いておきます。
――――――――――――

部分グラフの頂点の彩色に、一定の条件…①を課して
５色目が必要になったことをもって、
「４配色可能」であることと矛盾する。

という論法を、何の証明もなく使っているが、

実際は、①の条件下で５色目が必要だとしても、
「４配色可能」であることは有り得るわけで、
何も矛盾はしない。

――――――――――――

良く考えなおしてみてください。

**１３２人目の素数さん** · 2011/03/20(日) 02:22:15.14

2年前のスレと同じ展開だったな

**１３２人目の素数さん** · 2011/03/20(日) 10:56:44.20

独り善がりとはこの事だなｗ

**帰納と類比** · 2011/03/20(日) 11:16:43.21

>>33
１年前と同じ展開になりましたね。
>ある特定の条件では５色以上必要なグラフでも、
>全ての頂点の色を付け直して、上手く配色しなおすことで４色塗り分け可能であれば、
>そのグラフは４配色可能であります。

「そのグラフは４配色可能であります。」の根拠はどこにありますか。
まだ４配色可能と決まっているわけではありません。
５配色が可能ならわかりますが。
５配色が必要なグラフが存在するということを矛盾の根拠にしています。
そのグラフをうまく配色しなおしても、４配色可能ということは出来ません。
任意のグラフ全てが４配色可能だと言っているようなものです。
>>34　そうみたいですね。

**１３２人目の素数さん** · 2011/03/20(日) 12:12:23.94

>>36
４色配色可能な根拠って・・・

貴方が、一番初めに、「N-1個の頂点は４配色可能であるとする」
と仮定したんでしょ。多分、帰納法したかったんでしょ。

その後、なんか「接合」とかいう訳の分からない操作をした結果、
一時的にでも５色目を使った。

そして、その結果として、始めに「４配色可能であるとした仮定に矛盾する」とした。

そもそも「矛盾したから何をいいたいのか？？仮定が偽であるといいたいの？」
等という根本的な疑問はおいておいて、

「接合という操作の結果」５色目が必要になることと、
４配色可能であることは別に何も矛盾しない。

これ以上言ってもわからないようだったら、もうあきらめろよ。

――――――――
ちなみに、>>34,35は私じゃないからね。
>>34,35に完全に同意はしてるがｗ

**帰納と類比** · 2011/03/21(月) 23:37:20.50

>その後、なんか「接合」とかいう訳の分からない操作をした結果、
>一時的にでも５色目を使った。

接合を使って５色目を使ったので、Ｎ－１点以下は４配色可能という仮定に反すると結論付けました。
反例を一時的発生させて、４配色可能という仮定に矛盾するから、別の配色があって仮定と矛盾しないと
結論を導きました。それがＡＣチェーンあるいはＡＤチェーンが切れているグラフが存在すると結論付けました。
これはＮ－１点でP1，P2，P3，P4，P5が３配色可能と結論付けました。
従って、５集点は可約と結論付けました。
接合を使ったのは反例を導き出したかったからです。
接合はグラフではコントラクト（縮約）で普通の操作です。
>>37　これ以上言ってもわからないようだったら、もうあきらめろよ。
諦められません。
この辺が理解できる人いませんか。

**１３２人目の素数さん** · 2011/03/22(火) 00:05:17.37

いませんか、じゃなくてあんたが理解しなきゃならないんじゃないの？

>接合を使って５色目を使ったので、Ｎ－１点以下は４配色可能という仮定に反すると結論付けました。

>>37は、それが結論付けられないと言っている。

**１３２人目の素数さん** · 2011/03/22(火) 06:33:49.04

>>38
最初 N-1点までの地図が塗りわけ可能と仮定して、矛盾を導いたと主張してるんだよね？
そうすると、たとえば N=10 とすると、9点以下の地図の中に反例が存在するはず
これのおかしさは分かる？

**帰納と類比** · 2011/03/22(火) 18:03:36.84

>>40
Ｎが小さいときには、手作業で確認できるから、反例は存在しない。
Ｎが大きくなると確認のしようがないから、チェーンで確認する。
ＡＣチェーンとＡＤチェーンの片方が繋がってないと証明するには
両方が繋がっているとＮ－２点で５色目が必要になって、仮定と
矛盾すると言うしかない。この作業は数学的には当然のことと思います。

**１３２人目の素数さん** · 2011/03/22(火) 18:19:40.01

数学以外の世界ではそうなの？

**１３２人目の素数さん** · 2011/03/22(火) 18:23:30.86

>>41
そもそも、「背理法」なの？それとも、「帰納法」なの？

**帰納と類比** · 2011/03/22(火) 20:32:07.76

>>43
背理法を使った帰納法です。
５色目が必要になるが背理法で、全体は帰納法です。

**１３２人目の素数さん** · 2011/03/22(火) 20:48:35.45

>>44
背理法の「５色目が必要になる」を先に仮定したの？
「頂点がN-1個のグラフを４配色可能とする」を先に仮定したの？

**帰納と類比** · 2011/03/22(火) 22:30:16.83

「頂点がN-1個以下のグラフを４配色可能とする」を先に仮定しました。

**１３２人目の素数さん** · 2011/03/23(水) 22:50:25.14

>>41
つまり、手作業で確認できないくらい巨大な地図には反例が存在するわけね？
そうすると、4色定理を証明したんじゃなくて、
4色定理が正しくないってことを証明したわけだ

**帰納と類比** · 2011/03/24(木) 00:54:53.53

>>47
>巨大な地図には反例が存在するわけね？
Ｎ－１点以下では背理法で矛盾すると言ってる訳で
巨大な地図にも４配色可能だと言っています。
分からないかなこの論理。

**１３２人目の素数さん** · 2011/03/24(木) 01:18:10.12

>>48
「N-1点以下の地図が塗りわけ可能と仮定して矛盾を導いた」
のなら、当然、N-1点以下の地図に塗りわけ不可能なものが存在する
つまり、反例が存在するということになる

**帰納と類比** · 2011/03/24(木) 02:00:57.81

>>49
矛盾するといっても最初のＮ－１点以下は４配色可能と仮定してるので
ＡＣチェーンあるいはＡＤチェーンのいずれか切れていて、矛盾は解消される
と言いたいんだが。分かりますか。背理法で矛盾は誤りであると結論付けています。

**１３２人目の素数さん** · 2011/03/24(木) 02:21:59.35

>>50
A～CとA～Dが両方ケンペ鎖でつながってることなんて珍しくないと思わないか？
つながってる例はいくらでも構成できるんだけど
それとも、手作業で確認できないくらい巨大な地図だと絶対に切れてるの？

**帰納と類比** · 2011/03/24(木) 21:46:20.85

>>51
Ｎ－１点以下のグラフではＡＣチェーンかＡＤチェーンのいずれか一方は切れてる
配色が１つ以上存在することを述べている。
それが背理法で証明できた、と言っている。
両方繋がっているグラフも存在するかもしれないが、片方切れているグラフは
必ず存在すると証明している。
もし両方繋がっているグラフしかなければコントラクト（接合）して５色目が
必要になるが、背理法の仮定で４配色可能としているのでＡＣまたはＡＤチェーン
のいずれか一方のチェーンは切れている配色は１つは存在することになる。

**１３２人目の素数さん** · 2011/03/25(金) 00:22:38.74

>>52
> 両方繋がっているグラフも存在するかもしれないが、
だから、両方つながってる場合は、それが4色定理の反例になるはずでしょって聞いてるんだけど

**帰納と類比** · 2011/03/25(金) 00:54:29.53

>>53
両方繋がっている場合は有るかも知れないが、Ｎ－２点で反例が生ずる
ことになるので、Ｎ－１点以下では４配色可能と言う仮定に反する。
Ｎ－２点で反例は無いので（仮定より）、全ての配色でＡＣまたはＡＤ
チェーンの片方または両方の繋がっていないグラフは１つは存在する。

**１３２人目の素数さん** · 2011/03/25(金) 01:23:07.11

>>54
あるかもしれないが、仮定に反するとか言われても何言ってるか分からん

・両方つながってる場合はあるかもしれない(ないとは言えない)
・両方つながってるとしたら、仮定に反するので、両方つながってることはありえない

のどっちなのかはっきりして

**１３２人目の素数さん** · 2011/03/25(金) 02:13:49.95

>>52
あるグラフが四彩色可能であるとき、そのグラフに「接合」という操作を行った
ものが常に四彩色可能であることが証明されていなければ、その矛盾は
導けないと思うが？
つか、「接合」すると五色必要になると言っているんだよな？

**１３２人目の素数さん** · 2011/03/25(金) 02:30:08.10

>>56
> 四彩色可能であることが証明されていなければ、
N点より小さいグラフが4彩色可能なことは数学的帰納法の仮定だから、
そこは別にいいんじゃないか？

**帰納と類比** · 2011/03/25(金) 04:43:04.34

>>55
>・両方つながってる場合はあるかもしれない(ないとは言えない)
が正しい。
しかし、背理法により片方が切れているグラフは１つは存在する。
>>56
ＡＣまたはＡＤチェーンが両方繋がっている配色しか存在しないと
したら、５色目は必要であるが、帰納法の仮定でＮ－１点以下は
４配色可能だから、仮定と矛盾する。よってチェーンのどちらかが
切れている配色が１つは存在する。

**１３２人目の素数さん** · 2011/03/25(金) 07:34:02.26

まだ頑張ってるの？（笑

**１３２人目の素数さん** · 2011/03/25(金) 09:42:54.74

>>58
少なくとも一方が切れてる場合は、
ケンペと同じ論法でもとのN点のグラフが塗り分けられるからOK
こっちは問題にしてない

両方つながってる場合は、>>6 の理屈だと、「接合」を行ったN-2点のグラフは
塗りわけ不可能で、>>58 によればこの可能性は排除できない

つまり、塗り分けられる場合もあるけど、塗り分けられないグラフが存在する
可能性は排除できない
これじゃ証明になってないじゃん

**帰納と類比** · 2011/03/25(金) 18:49:25.92

ある任意のグラフでＮ－１点以下のグラフは４配色可能な配色が１つは
存在するということ。
>・両方つながってる場合はあるかもしれない(ないとは言えない)
は全ての配色を言っているのではない。片方切れている配色が必ず存在する。

**１３２人目の素数さん** · 2011/03/25(金) 20:12:09.18

不可避集合って何？
グラフ理論のお勧めの数学書を教えてくだされ。

**帰納と類比** · 2011/03/25(金) 22:12:35.28

>>62
ロビン・ウィルソン著　茂木健一郎訳
「四色問題」
P176
不可避はその中の少なくとも１つが全ての地図に現れるような配置の集合。

**１３２人目の素数さん** · 2011/03/25(金) 22:32:49.23

茂木健一郎って脳タレの人？

**帰納と類比** · 2011/03/25(金) 22:36:34.15

多分そう。

**１３２人目の素数さん** · 2011/03/25(金) 23:32:30.37

>>63
誤解されても仕方ない表現だなそれ

**１３２人目の素数さん** · 2011/03/25(金) 23:38:58.88

62ですが、数学書のほうではどれがお勧めでしょうか？
茂木のやつは読み物で、数学専門書ではないと思うのですが。
（今度読んでみますが）
グラフ理論入門 R.J. ウィルソンとかお薦め？
みなさんはどの本で勉強したのですか？

**１３２人目の素数さん** · 2011/03/26(土) 13:03:59.24

>>66
確かに誤解されても仕方ない表現だね。

そもそも茂木健一郎って、数学者じゃないでしょ。

**１３２人目の素数さん** · 2011/03/26(土) 14:56:10.77

いくらモギケンが馬鹿でもそんなこと書かないでしょと思って見たら、
本当に書いてあった…

**１３２人目の素数さん** · 2011/03/26(土) 15:08:20.83

>>61
最初にN点未満の地図が塗りわけ可能として、A～C、A～D が両方ケンペ鎖でつながっているとしたら矛盾を生じる
って論理を仮に認めたとしても、ここから言えることは、
「N点未満の地図に反例が存在する」かまたは
「A～C、A～D のケンペ鎖は少なくとも一方が切れている」
ということでしかない

**帰納と類比** · 2011/03/26(土) 21:00:27.56

>>70
与えられた任意のグラフはＮ－１点以下で４配色するのに幾つかの塗り方があって
そのなかに反例のような配色もあるが、ＡＣあるいはＡＤチェーンの切れている
塗り方が１つは存在するということ言っている。
従って、「A～C、A～D のケンペ鎖は少なくとも一方が切れている」配色が必ず１つは
存在する。

**１３２人目の素数さん** · 2011/03/26(土) 21:33:05.98

>>71
もし、A～C、A～D が両方ケンペ鎖でつながっているとしたら、
そのグラフで「接合」を行った N-2点のグラフは、4色で塗り分けられるのか、塗り分けられないのか、
yes か no かで答えてくれないか？

**帰納と類比** · 2011/03/26(土) 22:55:14.08

>>72
塗り分けられない。
がＮ－２点のグラフは４配色可能なので、仮定と矛盾し、別の塗り分けられる
配色が必ず存在する。この背理法は以前から何度も説明してきた。

**１３２人目の素数さん** · 2011/03/26(土) 23:19:17.68

>>73
> 塗り分けられない。
> がＮ－２点のグラフは４配色可能なので、
N-2点のグラフは塗り分けられないが4配色可能、つまり塗り分けられるのか？
何言ってるか分からないんだが

**１３２人目の素数さん** · 2011/03/26(土) 23:20:44.96

>>71
AからEまでの配色も任意という条件でA-C間がケンペ鎖で繋がっていない
配色なら当然存在し得るだろうが、それでは証明にならない。
一方で、何度も指摘されていることだけど、AおよびCに隣接する頂点の配色を
変更しないという条件で「接合」した結果5色目が必要になったとしても、N-1以下の
グラフが四彩色可能であることとは矛盾するとは言えない。

**帰納と類比** · 2011/03/26(土) 23:49:48.82

>>75
>AおよびCに隣接する頂点の配色を
>変更しないという条件で「接合」した結果5色目が必要になったとしても
変更してもよい。変更しても５色目が必要になる。
この辺は５集点をもとに再度考察してみてください。
少しややこしくなります。

**１３２人目の素数さん** · 2011/03/26(土) 23:55:00.66

Mr．Shiraishi が大昔に解いてただろ

**１３２人目の素数さん** · 2011/03/26(土) 23:59:40.34

考察してくださいも何も、なぜそうなるのかどこにも説明してないじゃん。
「AとCを接合すると5色になるので」って一言で済ませているけど、
それが無条件に成立すると言うのならそれを証明しないと。

**帰納と類比** · 2011/03/27(日) 00:15:22.95

>>78
その証明を追加すると別のグラフが必要で、うｐロダでもう１ページ追加
しなければうまく証明できない。言葉だけではうまく説明できない。
隣接する頂点の色を変えても、証明できる。
あなたにはそれを理解する能力が有りそうなので、考察してください。

**１３２人目の素数さん** · 2011/03/27(日) 00:21:32.21

「すべての平面的グラフは四彩色可能です。考察してください。」ってんじゃ
証明したことにはならないぞ。

**１３２人目の素数さん** · 2011/03/27(日) 00:23:58.65

>>74 に回答してもらいたいんだが

**１３２人目の素数さん** · 2011/03/27(日) 00:28:58.03

>>76
変更してもよい？AとCだった頂点の配色を変更して同色にできるなら
5色目は必要ないが？

**１３２人目の素数さん** · 2011/03/27(日) 00:40:18.19

>>81
このスレは、>>37-39で完了している。

帰納と類比が、論理を理解できないのが問題。

**１３２人目の素数さん** · 2011/03/27(日) 00:50:37.25

>>83
間違ってることを本人に理解させようっていうゲームが進行している

**帰納と類比** · 2011/03/27(日) 00:50:38.59

>>74
ＡＣとＡＤチェーンが結ばれているときは塗りわけできない。
５色目が必要になる。しかし仮定に矛盾するので、配色の１つはチェーンが
切れているものが存在する。
>>82
スクリプトを付けてもらわないと、どの人がどのレベルかわからない。
>>78の人かな。もう少し熟慮をお願いします。

**１３２人目の素数さん** · 2011/03/27(日) 01:20:24.27

自分の証明が正しいことを理解してもらいたい(か、あるいは間違いを正して欲しい)んじゃ
なかったのか？だったら説明が足りなくて他人に理解されない部分はちゃんと説明しないと。
それとも、単に「自分は正しい」と言いたいだけなのか？

**１３２人目の素数さん** · 2011/03/27(日) 13:23:58.38

帰納と類比の主張は

１俺の証明は正しい
２間違ってると思ったら１を読め

ということで良い？

**１３２人目の素数さん** · 2011/03/27(日) 13:50:23.75

無限ループ

**帰納と類比** · 2011/03/27(日) 21:42:34.84

どうして一人も証明を理解できないんだろう。
大学の数学科で助手以上の方居られましたらこの証明が正しいことを
理解できるだろう。学卒・現役学生じゃ無理みたい。
<<87　レスも含めて　１，２でいい。

**１３２人目の素数さん** · 2011/03/27(日) 21:59:50.11

グラフ理論以前に、論理に欠陥があるのだが…

**１３２人目の素数さん** · 2011/03/27(日) 22:15:29.73

>>89
大学で教えてても間違いは間違い

**帰納と類比** · 2011/03/27(日) 22:31:12.32

>>90
欠陥は修復できそうなことか？

**１３２人目の素数さん** · 2011/03/27(日) 22:55:59.77

「無理」って言っても (∩ﾟдﾟ)ｱｰｱｰｷｺｴﾅｲなんだろ？意味のない質問すんなよ。

**１３２人目の素数さん** · 2011/03/27(日) 23:53:20.48

>>どうして一人も証明を理解できないんだろう。

どうして間違っていることをあなた一人だけが
気づかないのか不思議だよ。

「特定の塗り方で5色必要になっても4色で塗れるという仮定に
反しない」
だからあなたの論法でACチェーンとADチェーンの両方が
つながっていても何の矛盾も生じない。

2年前から同じ部分の欠陥を指摘され続けているのにな。

**１３２人目の素数さん** · 2011/03/28(月) 00:32:57.46

IQが20以上違うと会話が成立しないというのを読んだ事がある。

**１３２人目の素数さん** · 2011/03/28(月) 00:39:01.49

>>95
蛸壺？

**帰納と類比** · 2011/03/28(月) 01:13:16.15

IQは１２０ですよ。普通のレベルなんだがな。
確かに会話が成立してないな。

**１３２人目の素数さん** · 2011/03/28(月) 01:24:58.87

日本人の平均は100くらいだそうですから
ボンクラとは会話が成立しないのも無理ありませんね

こう思われたかったのかしら

**１３２人目の素数さん** · 2011/03/28(月) 02:38:21.32

このスレの読者は一人を除くと140以上なのか

**猫は何も出来ない** ◆MuKUnGPXAY · 2011/03/28(月) 03:27:29.30

いや、ワシは100以下や。安心せい。

猫

べ · 2011/03/28(月) 05:18:16.73

俺180ぐらいあった気がする
まあ、神童と言われていたから妥当か…

**１３２人目の素数さん** · 2011/03/28(月) 05:56:24.89

藤原一宏教授の虚偽申請は、日本の数学界に対する国民の信頼を裏切った、
無視することのできない重大な事件です。このような者がのうのうと責任ある教授職を
続けていることに、藤原氏がプロの学者であることを自覚しているのなら
なおさら疑問をかんじざるを得ません。今後二度とこのような事件が起きないように
するためにみなさんで建設的な議論をしましょう。

**１３２人目の素数さん** · 2011/03/28(月) 06:05:35.27

帰納と類比の証明見て、別証明法考え付いたぜ！

【４色定理の証明】
①N-1個の頂点のグラフでは、４色塗り分け可能だと仮定する。
②全ての極大平面グラフは、３集点、４集点、５集点のグラフのいずれかを部分グラフとして含む。
③３集点を部分グラフとして含む場合、中央の点を除いたグラフを４色で塗り分けで、中央の頂点を
　その３つの隣接点とは別の色で塗り分ければいい。
④４集点、５終点についても、③と同様に、中央の点を除いたグラフについて、４色を使って塗り分ける。
　そして、中央の点を戻す際、その４つ、５つの隣接点と違う色で塗ることが出来れば、問題ない。
⑤④において、隣接点と違う色で塗ることが出来ないのは、①と矛盾する（笑。だから考えなくていい（爆
⑥よって、全てのグラフは、４色塗り分け可能である(｀・ω・´)キリッ

帰納と類比には、この証明法が正しいと理解できるはずだ！

**１３２人目の素数さん** · 2011/03/28(月) 06:28:16.66

藤原一宏教授の虚偽申請は、日本の数学界に対する国民の信頼を裏切った、
無視することのできない重大な事件です。このような者がのうのうと責任ある教授職を
続けていることに、藤原氏がプロの学者であることを自覚しているのなら
なおさら疑問をかんじざるを得ません。今後二度とこのような事件が起きないように
するためにみなさんで建設的な議論をしましょう。

**１３２人目の素数さん** · 2011/03/28(月) 13:15:26.26

>>36
>そのグラフをうまく配色しなおしても、４配色可能ということは出来ません。
↑
「うまく配色しなおせば４配色可能である」ことが「４配色可能」の定義そのものなんだよ。
グラフ理論の基本事項を完全に誤解してるじゃないか。

>任意のグラフ全てが４配色可能だと言っているようなものです。
↑
だからそれを証明しろってのが四色問題の定義だろ。
問題そのものを否定してることに気づいてるか。

自分の「証明もどき」に都合のいいように勝手に定義を変える。
これはトンデモ系によくあること。

これでよくハーバードだのIQ120だの言えるな。
世界中どこの機関に送ってもこんな論文は即却下だよ。
おそらく返事すら貰えないレベル。

**１３２人目の素数さん** · 2011/03/28(月) 16:23:58.85

>>1
あなたの証明の大まかな方針は細部を以下のようなもので
あっている?

(1) N-1 個の頂点の任意のグラフは4色で塗り分け可能と仮定する.
このとき N 個の頂点を持つグラフも4色で塗りわけ可能であることを
　　示す. そうすれば帰納法により目的達成.

(2) N 個の頂点のグラフが 5集点を持つ場合を考える. 仮に
真ん中の頂点を (f) とし周りの5つの頂点を (a)～(e) とする.

元のグラフから頂点 (f) を取り除いた N-1 頂点のグラフを考える.
この N-1 点のグラフの4色での塗り分けで以下のようなものが
存在することを示す:
「(a)～(e) の色の配置が, 頂点 (f)を加えたときに、容易に (f) も
塗り分けられるようになっている」

単に4色で塗り分け可能であることは帰納法の仮定から分かる
ので, 塗り分けられないような都合の悪い配色はそもそも
存在しないことを背理法で示す.
　　
(3) そのような配色になっていたとせよ. するとそこからある操作をして得られる
N-2 個の頂点のグラフの塗り分けには5色が必要になり帰納法の仮定に
矛盾する. よってそのような配色はありえない.

**１３２人目の素数さん** · 2011/03/28(月) 18:51:04.57

失礼, >>106 の出だしの文章, 変だね.

誤: 細部を以下のようなもので～
正: 細部は別として, 以下のようなもので～

**帰納と類比** · 2011/03/28(月) 20:33:49.62

>>106
>(2) N 個の頂点のグラフが 5集点を持つ場合を考える. 仮に
>真ん中の頂点を (f) とし周りの5つの頂点を (a)～(e) とする.

>元のグラフから頂点 (f) を取り除いた N-1 頂点のグラフを考える.
>この N-1 点のグラフの4色での塗り分けで以下のようなものが
>存在することを示す:
>「(a)～(e) の色の配置が, 頂点 (f)を加えたときに、容易に (f) も
>【4色で】塗り分けられるようになっている」
とは限らない。
>Ｎ－１点で>単に4色で塗り分け可能であることは帰納法の仮定から分かる
>ので, 【(a)～(e)を３色で】塗り分けられないような都合の悪い配色はそもそも
>存在しないことを背理法で示す
上記のように修正したいです。
(1)(3)はそのままでよい。

**帰納と類比** · 2011/03/28(月) 20:35:51.68

>>106
>(2) N 個の頂点のグラフが 5集点を持つ場合を考える. 仮に
>真ん中の頂点を (f) とし周りの5つの頂点を (a)～(e) とする.

>元のグラフから頂点 (f) を取り除いた N-1 頂点のグラフを考える.
>この N-1 点のグラフの4色での塗り分けで以下のようなものが
>存在することを示す:
>「(a)～(e) の色の配置が, 頂点 (f)を加えたときに、容易に (f) も
>【4色で】塗り分けられるようになっている」
とは限らない。
>Ｎ－１点で>単に4色で塗り分け可能であることは帰納法の仮定から分かる
>ので, 【(a)～(e)を３色で】塗り分けられないような都合の悪い配色はそもそも
>存在しないことを背理法で示す
上記のように修正したいです。
(1)(3)はそのままでよい。

**帰納と類比** · 2011/03/28(月) 20:46:13.24

>>103
Ｎ点を戻すと仮定から反する。Ｎ－１点なら４配色可能。

**１３２人目の素数さん** · 2011/03/28(月) 22:52:20.53

だったらこれならどう？

隣合う2頂点とそれを囲むサイクルを考える。
このサイクルが4彩色されている場合、この2頂点を縮約すると5色目が必要になる。
これはN-1のグラフが4彩色可能であるという仮定に反するので、隣合う2頂点を囲むサイクルは
高々3彩色であることがわかる。
3彩色のサイクルに囲まれる2頂点は、残る1色を割り当てた1頂点に縮約することができる。
以上より、隣合う2頂点は可約であることが証明できた。

**１３２人目の素数さん** · 2011/03/28(月) 23:12:26.35

>>73,85
「N-2点のグラフは塗り分けられないが、4配色可能」と言ってると理解していいのか？
「塗り分けられる」と「4配色可能」ってのはどう違う？

**帰納と類比** · 2011/03/28(月) 23:23:14.82

>>111
>3彩色のサイクルに囲まれる2頂点
を縮約するのではなく、2頂点のまま3彩色のサイクルの中で４彩色
できなければ、隣合う2頂点は可約であると言えない。
縮約してしまうと、Ｎ－１点のグラフになってしまう。

**帰納と類比** · 2011/03/28(月) 23:32:35.18

>>112
>N-2点のグラフは塗り分けられないが、背理法後4配色可能となる
「塗り分けられる」＝「4配色可能」

**１３２人目の素数さん** · 2011/03/28(月) 23:47:06.35

しまった、詰めが甘かったか(///)
しかしあくまでも、前段の「隣合う2頂点を囲むサイクルは高々3彩色」って
ところには突っ込まないんだなｗ

**１３２人目の素数さん** · 2011/03/29(火) 01:20:30.93

>>114
背理法によって塗り分けられることを示したのは最初の N点のグラフじゃないのか？
N-2点のグラフも「背理法後」塗り分けられるようになるのか？

**帰納と類比** · 2011/03/29(火) 01:37:11.49

>>116
はいそうです。

**１３２人目の素数さん** · 2011/03/29(火) 01:47:21.61

>>117
N-2点のグラフは塗り分けられないが、「背理法後」はその同じグラフが塗り分けられるようになるのか？

**帰納と類比** · 2011/03/29(火) 01:52:30.94

>>118
配色を変えて、同じグラフが４配色可能となる塗り方が１つは存在します。

**１３２人目の素数さん** · 2011/03/29(火) 06:07:35.96

>>108
結局、どう修正したいの？

【4色で】と【(a)～(e)を３色で】を補えばOK?

それとも下から6行目の「とは限らない」も補うの？

**帰納と類比** · 2011/03/29(火) 07:34:15.49

>>105-110
過去レスを見るにはどうしたらいいですか。
もう一回見て回答したい。

**帰納と類比** · 2011/03/29(火) 07:58:46.24

>>120
【4色で】と【(a)～(e)を３色で】
下から7行目の【とは限らない】も補う
と>「都合の悪い配色はそもそも存在しないことを背理法で示す」を削除

【東電 86.0 %】 · 2011/03/29(火) 10:21:36.26

あ

**１３２人目の素数さん** · 2011/03/29(火) 13:30:26.75

>>122
[(a)～(e)を３色で] を補う先の「都合の悪い配色は～」という
一文を削除するの？
指示通りに書き直すと文章にならないんだけど？

中途半端な「加える」とか「削除する」とかいう指示じゃなくて
>>106 の (2) にあたる部分を自分なりに
書き直した完全な文章を提示してもらえませんか?

**１３２人目の素数さん** · 2011/03/29(火) 15:47:13.18

>>106
パッと見(3)で証明として論理破綻してるよなｗｗ

**１３２人目の素数さん** · 2011/03/29(火) 20:34:57.77

俺一人が正しいって思っている奴を説得するのは無理だよ

**１３２人目の素数さん** · 2011/03/29(火) 20:56:01.76

帰納と類比vs猫はまだ？

**帰納と類比** · 2011/03/29(火) 21:42:34.45

5集点は不可避集合である。
Ｎ－１点までのグラフは４配色可能であると仮定する。
Ｎ点の任意のグラフにある５集点に着目する。
５集点の中央の頂点P0とその辺を仮に削除する。
このＮ－１点のグラフは仮定より４配色が可能である。
P0の周りの頂点をP1～P5とする。
P1～P5の頂点は４色で塗られている。
５つ頂点の内同じ色のものを色Ｂとする。
色Ｂと色Ｂに囲まれた一個の頂点をP1とする。
P1の色をＡとしP2，P5を色Ｂにする。
残った色ＣをP3，色ＤをP4とする。
仮にP1～P5が３色で塗られていれば、P0を戻してＮ点で４配色可能となる。
上記P1～P5が４色でＣをＡに変えられない、ＤをＡに変えられないとする。
ケンペ鎖ではＡＣチェーン、ＡＤチェーンが繋がっているとする。
ＡとＣをコントラクトしてＮ－２点のグラフを得る。
このとき頂点Ａは頂点Ｃと結合するのでＡ，Ｃ以外の色で、頂点ＡはＢに
辺で接しているので、Ｂ以外の色、頂点ＣはＤに接しているのでＤ以外の色
を要求される。５色目のＥが必要となる。
同様にＡとＤをコントラクトしてＮ－２点のグラフを得た場合
５色目のＥが必要になる。
Ｎ－１点以下のグラフは４配色可能なのでＮ－２点でも４配色可能となる。
しかし仮定に反し５色目が必要になった。
これはＮ－１点以下のグラフが４配色可能と言うことに矛盾する。
従ってＡＣチェーンまたはＡＤチェーンが切れているグラフが１つは存在
しなければならない。
よってP1～P5を３色で配色することができる。
よってＮ－１点のグラフが４配色可能であればＮ点のグラフも４配色可能である。
よって帰納法が成立し、平面状のグラフは４配色可能である。

**１３２人目の素数さん** · 2011/03/29(火) 22:11:04.78

>同様にＡとＤをコントラクトしてＮ－２点のグラフを得た場合
>５色目のＥが必要になる。
>Ｎ－１点以下のグラフは４配色可能なのでＮ－２点でも４配色可能となる。
よって５色目のＥが必要になると思ったのは間違いだった。

**１３２人目の素数さん** · 2011/03/29(火) 22:51:36.16

>>128

言葉がよく分からんが, 例えば下の彩色された
グラフは AC チェーン, AD チェーンが繋がっている
ということでいい?
(括弧つきは考えている5点以外の頂点, A,B,C,D は色)

　　　(C)--A--(D)
　　　　　／　＼
　　　　B　　　　B
　　　　|　　　　　|
(A)---C-----D---(A)

で A と C の色の頂点をくっつけて一つにする
(その頂点を○で表す)

　　(C)　　(D)
　　　＼／
　B---○---B
　　　／＼／　
　(A)　　　 D--(A)

すると A, B, C, D の色の塗られた頂点と繋がってるから,
丸で示した頂点を塗るには第5の色 E が必要になる.
点の数が N-2 点 (この場合は N=10 だね) だから
帰納法の仮定から４色で塗り分け可能なはず.
矛盾!! というのが主張ってことでいい?

**１３２人目の素数さん** · 2011/03/29(火) 22:53:35.68

でも、実際には >>130 には何の矛盾もない.

上の例では, 例えば下のようにすれば4色で塗り分け
可能だから.

　　(A)　　(A)
　　　＼／
　B---C ---B
　　　／＼／　
　(A)　　　 D--(A)

ということを皆、繰り返し言ってるんだと思うんだけど.

**１３２人目の素数さん** · 2011/03/29(火) 23:13:35.01

言葉が通じないのであくまでも推測だけど、上の2つの塗り分けでは
(A)-(C)のケンペ鎖が繋がっているが、最後の図のような塗り分けは存在して
そのときそのケンペ鎖は繋がっていない、という主張じゃないかと思う。

**帰納と類比** · 2011/03/29(火) 23:35:13.30

>>131
まだ理解してないな。
>>130
その理解で正しい。
「- - -(C)--A--(D) -|
|　　　　／　＼ |
|　　　B　　　　B |
|　　　|　　　　| |
(A)---C-----D---(A) 」
図がうまく描けてないかな、上のようなイメージ。

**１３２人目の素数さん** · 2011/03/29(火) 23:55:46.11

>>130と>>131は同じ人じゃねえの？

**１３２人目の素数さん** · 2011/03/29(火) 23:58:46.27

>>132
なるほど.
ようやく証明の流れが分かったような気がする.

「考えている N-1 点のグラフの『任意の』 4色塗り分けに対して,
P1～P5 を塗るのに4色使われていて, かつ AC チェーン, AD チェーンが
繋がっているとせよ.

そうすると, A と C, あるいは Aと D を「接合」して得られる N-2 点の
グラフの塗り分けに5色必要」

となるから矛盾, といいたいわけか. すると多分,

命題: 「N-2 点のグラフの『全ての』4色での塗り分けは,
元のN-1点グラフの4色を用いた『ある』塗り分けから上記の
操作で得られる」

ということが成立すると思っているのね.

これは自明じゃないから、これを示さないと何も証明したことに
ならないよ.

>>134
うん, 同じ人. 改行多すぎると怒られたから分けただけ.

**帰納と類比** · 2011/03/30(水) 08:49:55.87

>>135
>命題: 「N-2 点のグラフの『全ての』4色での塗り分けは,
>元のN-1点グラフの4色を用いた『ある』塗り分けから上記の
>操作で得られる」

>ということが成立すると思っているのね.

>これは自明じゃないから、これを示さないと何も証明したことに
>ならないよ.

これは自明なんだがな。Ｎ－２点のグラフはＮ－１点の接合で得られる。

**１３２人目の素数さん** · 2011/03/30(水) 09:04:35.15

>>136
自明だというなら, 証明してください.

**１３２人目の素数さん** · 2011/03/30(水) 15:36:37.18

ここって、帰納と類比の頭の中を暴くスレですか？

**１３２人目の素数さん** · 2011/03/30(水) 20:49:40.90

>>119
色を全部チャラにして白紙の状態から塗りなおせば、塗り分けられるってこと？

**帰納と類比** · 2011/03/30(水) 22:53:01.35

>>135
上記の操作ではなく、３集点を追加してＮ－１点のグラフにすればいい。
上記の操作にこだわる理由はどこにあるの？
上記の操作では５色目が必要になる場合があり、矛盾を生じる。
訂正：>>136
与えられた命題は正しくはない。

**１３２人目の素数さん** · 2011/03/30(水) 23:51:44.91

>>140

>上記の操作では５色目が必要になる場合があり、矛盾を生じる。

え?
単に「5色目が必要になる場合がある」っていうのが,
「4色で塗り分け可能」という仮定と反すると, この期に及んでも
本気で思ってたの?

>訂正：>>136
>与えられた命題は正しくはない。

そうですか.
正しくないと断言するなら, 反例を示していただけ
ますか?

その反例が, あなたの4色問題の証明の不備を
明らかにするはずですから.

**帰納と類比** · 2011/03/31(木) 20:27:06.17

>>141
今までのレスをしっかり読んでください。
>>128, >>130

**１３２人目の素数さん** · 2011/03/31(木) 20:42:41.09

>>142
えっ？
私は 141 だけど, >>128 を読んだ上で
>>130 を書いた本人だよ？　
(ついでに >>131, 135 もね)

ひょっとして >>130 をあなたの応援演説のように
でも思ってるの？
あなたこそしっかりと今までのレスを読みなよ.

>>130, 131 は一続きで, >>128 の書き込みが
とんでもない間違いを言っているとしか思えない、
というのがその主張だよ.

**帰納と類比** · 2011/03/31(木) 22:46:45.20

>>131は間違いだよ。
そのような塗り方は存在しない。
だからＡＣとＡＤチェーンが結ばれていれば、５色目が必要になる。
何度も言ってるんだが分からないかな。
もし塗れるとしたら>>131の配色の手順を述べて欲しいものだ。

**１３２人目の素数さん** · 2011/03/31(木) 23:09:20.70

>>144
手順も何も・・・
>>131 に書いてある図が4色での塗り分け
じゃないとでもいうの?

もし >>133 でいうような例がお好みなら,
A と C の頂点を接合すると

--(C)　　(D)--------
|　　　＼／　　　　　　|
|　B---○---B　　　 |
|　　　／＼／　　　　|　
--(A)　　　 D--(A)--

この「グラフ」は4色で塗り分けられる:
例えば

--(C)　　(D)--------
|　　　＼／　　　　　　|
|　A---B ---A 　　 |
|　　　／＼／　　　　|　
--(A)　　　 D--(A)--

上の図のB色を A色で勝手に塗り変えるな,
なんて言うなよ?

帰納法の仮定で保証している
「N-1 点までのグラフは4色で塗り分け可能」と
いうのは, 「4色での塗り分けが少なくとも一つ
存在する」というだけの意味なんだから.

**帰納と類比** · 2011/03/31(木) 23:55:09.40

>>145
ちょっと時間をください。
よく検討してみます。
1週間くらいかかるかな。
上記図は特殊な場合に成立する。一般的でない。ある条件が必要。
この場ではここまでにして保留にする。

**１３２人目の素数さん** · 2011/04/01(金) 22:44:57.12

前スレとか読んでなくって、場違いな質問になりますが、
何かご存知のことがあれば教えてください。

以下の命題が正しいとすれば、グラフ理論におけるテイト定理(3正則な平面グラフの辺彩色は3彩色的である)を直接的に証明できます。
テイト定理⇔四色定理なので、逆に四色定理から、下記の正しさを導き出すことができないか?
そして、もし、四色定理に帰着できるならば、次数を限定化した四色定理(つまり、次数N以下の平面グラフ)に帰着させることはできないか？
（例えば、次数5以下の平面グラフで四色定理が成り立つことは、五色定理から簡単に導かれますよね？）

などと言うことを考えています。

反例や未解決であることのソースなんでもいいので情報をください。

以下は命題です。

-----------------------------------------------------------
命題※

頂点彩色が3彩色可能な平面グラフGについて

3色を用いてどのような塗り分けを行っても同じ色にしか塗り分けできない点の集合を「同色点集合」と定義する。

※明らかに同色点集合であることの必要条件は独立点集合(安定集合)であることである。

このとき、以下の命題は常に真か?

3彩色可能な平面グラフGについて、任意の同色点集合から次数3以下の点を3つを選び出し、それら3点を
結ぶ辺を追加したグラフG'が平面的ならば、平面グラフGには次数6以上の点が存在する。

**１３２人目の素数さん** · 2011/04/01(金) 22:45:39.84

テイト定理証明の流れ(上記を正しいと仮定した上で)

1.次数3,4,5の点の双対グラフを考える。
これらは、3正則な平面グラフにおいて不可避集合である。
　(3正則な平面グラフの双対グラフは極大平面グラフだから)

2.次数4の点の双対グラフについて
　これは、周り4本の辺をどのように彩色しても
　内部は3彩色可能である。ところで、3正則な平面グラフにおいて
　3彩色不可能であるようなグラフのうち最も小さいグラフを
　最小反例と定義する。最小反例は1つでも点を除去すれば、
　3彩色可能である。次数4の点の双対グラフを除いたグラフが
　3彩色的ならば、加えたグラフも3彩色的であるため、
　次数4の点の双対グラフは　最小反例には含まれない。
　このような配置を可約配置と定義する。

**１３２人目の素数さん** · 2011/04/01(金) 22:46:00.49

3.次数3の点の双対グラフ(a)について
　これは、周り3本の辺が全て同色の時のみ3彩色できない(証明略)
　ここで、3正則な平面グラフのライングラフを考える。
　このグラフは、4正則な平面グラフ(*)である(証明略)
　最小反例に(a)が存在すると仮定し、そのライングラフを考える。
　最小反例から(a)除いたグラフは、3彩色可能である。
　このとき、(a)に接合していた3点に着目すれば同色点集合である
　ことがわかる。再び(a)をもどし、適当に縮約と削除を行えば、
　それら3点を結ぶ3角形ができる(証明略)。平面グラフのマイナーは
　平面グラフである。3点全てが同一の同色点集合に含まれるならば
　命題※より次数6を含むことになるが、これは(*)と矛盾する。
　よって、少なくとも1つは同色点集合に含まれない。
　このことから、周り3本の辺が全て同色になる以外の塗りわけが
　少なくとも1つ存在するため、3正則な平面グラフに配置(a)が
　存在する時、配置(a)は可約配置である。

4.次数5の点の双対グラフについて
上記とほぼ同様の方法で可約配置であることが証明できる。

5.締め
　このことより、3正則な平面グラフには少なくとも1つは可約配置を
　含むため、最小反例は存在しない。よって、3正則な平面グラフの
　辺彩色は3彩色的である。

6.さらに
　正則な平面グラフの辺彩色が3彩色的ならば、あらゆる平面グラフは
　２つのサイクルの合併である。

　よって、あらゆる平面グラフは4 彩色的である。

**１３２人目の素数さん** · 2011/04/01(金) 22:46:46.75

正確には「どんなブリッジをもたない」が必要だと思いますが
その辺は読み替えてください。

上記のアプローチはあまりにもシンプルで四色定理の証明について
テイト彩色からのアプローチは19世紀から主流だったことから、
このアプローチはかなり昔に既に考えられていてもおかしくないの
ではないかとおもっています。

だとすると、

1.今まで誰も考えたことなかった発想(・・・それはないだろ?)
2.命題※の証明は未解決で四色定理と同等以上に難しい。
3.そもそも命題※は間違っている(そうでないことを祈りたい)
4.そもそも命題※は証明できない(そうでないことを祈りたい)

になるので、2.であると信じて近年証明された定理や予想を
探して考えているのですが、命題※が証明できる気がしません。
(私が証明したいのは命題※であって四色定理ではない)

なにかご存知のことがあれば教えてください。

でも、ここまで言って簡単に(しかも否定的)に解決されたら・・・

私は自分の間抜けさに絶望して、スフィンクスに倣うしかなくなるかも知れません。

**１３２人目の素数さん** · 2011/04/02(土) 00:16:42.83

>>147
> 3色を用いてどのような塗り分けを行っても同じ色にしか塗り分けできない点
こういう点は存在しないと思うが？

**１３２人目の素数さん** · 2011/04/02(土) 00:29:14.03

> 3色を用いてどのような塗り分けを行っても同じ色にしか塗り分けできない点

ポイントは平面グラフの『4彩色』ではなく平面グラフの『3彩色』である点

例えば、1つの辺を共有する隣り合う3角形を考えた場合、次数2の点同士は常に同じ色でしか塗りわけできない(異なる色で塗るとグラフが4彩色されるため)。

**１３２人目の素数さん** · 2011/04/02(土) 00:48:04.07

>>151
同色点集合の定義を変えてみた。

頂点彩色が3彩色可能な平面グラフGについて

どのような塗り分けを行っても全ての要素が同一色になる独立点集合を
「同色点集合」と定義する(なんか記号使った方がいい?)。

**１３２人目の素数さん** · 2011/04/02(土) 01:11:06.99

>>148
> 1.次数3,4,5の点の双対グラフを考える。
双対グラフってのは点に対して定義されるものじゃなくて、グラフに対して定義されるものでしょ？

> 　これは、周り4本の辺をどのように彩色しても
> 　内部は3彩色可能である。
内部ってのはどこのこと？

**１３２人目の素数さん** · 2011/04/02(土) 01:14:19.43

スマン。流石にあいまいすぎるな。

＼　／
口
／　＼

の口の部分

**１３２人目の素数さん** · 2011/04/02(土) 01:18:52.26

>154
双対グラフってのは点に対して定義されるものじゃなくて、グラフに対して定義されるものでしょ？

それは思ったが文章で手っ取り早く流れ(要点)だけを説明したかったので。
この辺は図を使えばいくらでも正確に定義できるし、証明もできる
(言ってる意味は理解してもらえてると思う)。

**１３２人目の素数さん** · 2011/04/02(土) 01:26:30.39

３枝地図において三辺国，四辺国，五辺国は不可避非集合であるといった方が
文章的には分かりやすいだろうか?

**１３２人目の素数さん** · 2011/04/02(土) 01:56:40.44

もとのグラフ(地図)とその双対グラフが出てくるから、どっちを指してるのか分かりにくいんだよね
例えば
> 1.次数3,4,5の点の双対グラフを考える。
こういう書き方をしたら、「次数3,4,5の点」ってのはもとの地図の頂点みたいに読めるけど、
>>157 を見ると、実際は双対グラフでの頂点を指してるわけでしょ？

**１３２人目の素数さん** · 2011/04/02(土) 02:02:29.46

>>158
その通りです。この辺はもうちょっと整理すべきですね。
図をつければもうちょっと改善すると思う。

**１３２人目の素数さん** · 2011/04/02(土) 10:31:41.17

言い忘れてたけど、

3彩色可能な平面グラフGについて、任意の同色点集合から次数3以下の点を3つを選び出し、それら3点を
結ぶ辺を追加したグラフG'が平面的ならば、平面グラフGには次数6以上の点が存在する。

上記からオイラー公式を使って以下に言い換えることができる(むしろ上は下からの帰着)。

3彩色可能な平面グラフGについて、任意の同色点集合から次数3以下の点を3つを選び出し、新たに
点vを追加し、選び出した3点とそれぞれ辺で接合したグラフG'が平面的ならば、
平面グラフGには次数6以上の点が存在する。

言い換えれば(むしろ上は下からの帰着)

3彩色可能な平面グラフGについて、平面グラフGが次数5以下の点のみで構成される場合、
次数3の点に着目したとき、隣接する3点のうち少なくとも一つは同一の同色点集合に
属さない。

つまり、次数4以下の平面グラフの3彩色問題を考える上で有効だと思っています。
テイト定理の証明は上記の証明を考える過程で発見しました。なので、個人的に
あまり重要ではありません。

**１３２人目の素数さん** · 2011/04/02(土) 18:45:29.23

>>149

自己レスです。

>>このグラフは、4正則な平面グラフ(*)である(証明略)
　4正則であることはほぼ自明だが、平面的であることは
　自明だとは言えないので一応証明しておく。

3正則な平面グラフにおいて
点数を n, 辺数を mとすると

3正則なので、m=3n/2

生成されるライングラフにおいて
点数を n', 辺数を m'とすると、

n'=m=3n/2
m'=3n

n≧4の時、3n ≦ 9n/2 -6

ところで平面グラフの辺数の上限は

m'≦3n'-6

3正則グラフは、n≧4なので、3正則の平面グラフの
ライングラフは平面的である。

以上

**１３２人目の素数さん** · 2011/04/02(土) 19:33:46.63

スマン・・・上の証明間違っている。

ところで平面グラフの辺数の上限は平万グラフであることの
十分条件であって必要条件ではない。

K3,3を考えてもらうと分かるが、
n=6,m=9
3n-6=18-6=12

よって、m<3n-6だが、平面的ではない。

・・・なぜこれに気がついたかと言うと、上記証明が正しいとすると
ピーターセングラフ(辺彩色が4彩色的)のライングラフも平面的になり、
テイト定理の証明と命題※が正しいこと自体が根本的に間違っている
ことになってしまうため、かなり焦って考え直しました。

・・・平面的であることの証明は考え直して見ます。

**１３２人目の素数さん** · 2011/04/02(土) 22:03:46.44

>>161

3正則な平面グラフのライングラフが平面的であることの証明

3正則な平面グラフにおいて
点数を n, 辺数を m, 面数をfとすると

n+f=m+2
m=3n/2

n+f=3n/2 +2

一方、生成されるライングラフにおいて
点数を n', 辺数を m'，面数をf'とすると

n'=m=3n/2
m'=3n
f'=f+n=3n/2 +2

n'+h'=3n/2 +3n/2 +2=3n+2=m'+2

∴n'+h'=m'+2

よって、3正則な平面グラフのライングラフは
平面的である。

以上

・・・マジで焦った。4正則であることは、3正則グラフは
1つの辺に4つの辺が隣接してることから明らか。

**１３２人目の素数さん** · 2011/04/02(土) 22:07:26.03

ちなみに、ピーターセングラフではn+f≠m+2なので、上記と同様の方法で
3正則な非平面グラフのライングラフは非平面的であることの証明もできます。

**帰納と類比** · 2011/04/03(日) 01:32:17.63

>>147-164割り込みすみません。

>>135,>>145

--(C)　　(D)--------
|　　　＼／　　　　　　|
|　B---○---B　　　 |
|　|　／＼／　　　　|　
--(A)　　　 D--(A)--

この「グラフ」は4色で塗り分けられない:
例えば

--(C)　　(D)--------
|　　　＼／　　　　　　|
|　A---B ---A 　　 |
|　|　／＼／　　　　|　
--(A)　　　 D--(A)--

ということで、ＡＢチェーンが切れてる場合にしか４配色できない。
特殊な場合を除いて５色目が必要となる。

**１３２人目の素数さん** · 2011/04/03(日) 02:26:39.60

>>165
もういいや.
さすがに, ここまでのアホの相手は時間の無駄だね.

あなたは「4色定理」を示そうとしてるんでしょ?
「4色定理」が正しければ, 塗り分けられないはずないじゃない.

--(C)　　(D)------
|　　　＼／　　　　|
|　C---B ---C　　|
|　|　／＼／　　　|　
--(A)　　 D--(A)--

ほーら, 塗り分けられた.

それにね, たとえ「特殊な場合を除いて５色目が
必要となる」ことが示せたとしても(示せてないけどね),
それに何の意味もないよ.

あなたの証明が正しいためには, その推論が
「全ての場合」にうまくいかなければならない,
うまくいく例を一つ見せても無意味.

他方, あなたの証明が正しくないことを示すためには
うまくいかない例を「たった一つ」示せばいい,

この程度の論理も分からないんじゃ, 数学はやめて
おいたほうがいいよ.

**１３２人目の素数さん** · 2011/04/03(日) 02:43:13.67

>>165
過去ログ読みました。
疑問に感じたことを書きます。

まず、彩色数が5の平面グラフを仮定し、そのうち最も
小さいものを最小反例と呼ぶことにします。最小反例は
可約配置を含まないため、バーコフのダイヤモンドや
次数4以下の点などの可約配置を含みません。

最小反例の頂点の数をnとおくと、明らかに頂点数がn未満の場合、
4彩色可能である。

ここで、最小反例よりも大きいグラフを考える。明らかに
彩色数が5の平面グラフは最小反例をマイナーに持つ。
また、最小反例をマイナーに持たない頂点数が多い
平面グラフは存在することは明らか。

よって、あなたの証明は最小反例の頂点数以下では成り立つ
のかも知れませんが、最小反例の頂点数を超えると成り立た
ないと考えられます。つまり、最小反例の頂点数をnとすると
n→∞であることの証明が必要だと思いますがどう考えられ
ていますか?

**１３２人目の素数さん** · 2011/04/03(日) 03:16:35.53

あとは最小反例について、次数5の点を5色目で塗り分けるだけで全体が
5彩色できることの証明ですね。つまり、最小反例内に存在する次数5の
点がnあるとし、5色目でしか塗りわけられない点の数がnを超えないことと
次数5の点に5色目を移動させる手順を教えてください。

**１３２人目の素数さん** · 2011/04/03(日) 03:24:03.07

>>167
> 明らかに
> 彩色数が5の平面グラフは最小反例をマイナーに持つ。
横から悪いけど、これは何故？

**帰納と類比** · 2011/04/03(日) 03:32:47.47

>>166
--(C)　　(D)------
|　|　＼／　　　　|
|　C---B ---C　　|
|　|　／＼／　　　|　
--(A)　　 D--(A)--

ほうら、塗りわけられない。
特殊な条件のもとでしか４配色できない。
どうして分かってくれないの？

**１３２人目の素数さん** · 2011/04/03(日) 03:36:53.03

>>169
自分で書いといてなんだが・・・・私も思った。
それがいえるんだったら、Hadwiger予想(k＝5)を証明して終わりだよね。

**１３２人目の素数さん** · 2011/04/03(日) 04:47:35.47

あとやっぱり、最後の手順で5色目が必要になる理由が分かりません。
「色の拘束」と言う概念は分かますし、そこで5色目が必要になることも
わかります。ですが、点数がN-1以下だと「色の拘束」を行っても
4彩色可能であることは何故いえるのでしょうか？仮定では単純に
点数がN-1以下は4彩色可能だとしか言ってないので・・・・よく分かりません。

でも、この方法の面白さは感じました。AとCの接合と言う概念を用いれば、
ケンペ鎖を使わなくても次数4の点が可約配置であることの証明ができますから
便利だと思います。

**１３２人目の素数さん** · 2011/04/03(日) 12:33:10.68

>>170
かわいそうになってきた.
辺をいくら増やしたって無駄なんだから.

--(C)　　(D)------
|　|　＼／　　　　|
|　D---B ---D　　|
|　|　／＼／　　　|　
--(A)　　 C--(A)--

ほら, ね.

それよりも >>166 の後半をよーく
読んでよ.

私は >>145 であなたの推論が正しくない例を
示した. それに反論したければ, 自分の推論どおりの
結果が出る例をいくら提示しても無意味
(提示すらできてないけど).

あなたのやるべきことは4色問題の
自称「証明」を修正することだよ.

**１３２人目の素数さん** · 2011/04/03(日) 13:39:40.93

>>170
>特殊な条件のもとでしか４配色できない。
>どうして分かってくれないの？

貴方の方が分かっていないのでは？
貴方の根本的な誤りは、
>>128前半(11行目まで)の彩色が、最小反例になっていると
仮定していることではないでしょうか。

他の人は「それは彩色の内の１つで、全ての彩色に適用されるわけじゃない」
と言っているのですが。

・・・と言っても、分かってもらえないと思うので
簡単な反例を出してみます。
┌─────┬─────┐
│　　　Ｃ　　│　　Ｄ　　　　 │
│　 ┌─┬─┴─┬─┐　 │
│　 │ 　│　　　　│　 │　 │
│　 │Ｂ │ 　◎　 │Ｂ│　　│
│　 │ 　│　　　　 │　 │　 │
│　 │ 　├───┤　 │　 │
│　 │ 　│　　Ａ　│　 │　　│
│　 │ 　├─┬─┤　 │ 　│
│　 │ 　│Ｃ │Ｄ│　 │ 　 │
│　 │ 　├─┴─┤　 │ 　│
│　 │　 │　Ａ　│　 │　　│
│　 └─┴┐ 　┌┴─┘ 　│
└────┴─┴────┘
これは、>>128の仮定をすべて満たしています
このままの配色では"◎"に5色目の配色が必要です。

上図の彩色の問題点は、A-C、A-Dのケンプ鎖ではなく、左右の"B"にあるのですが

**１３２人目の素数さん** · 2011/04/03(日) 14:16:58.22

>>174
予言しよう。
その例をみて帰納と類比は
「やっぱり5色目が必要だ。俺は正しい。
俺の理解者が現れた」
と言う。

**帰納と類比** · 2011/04/03(日) 14:24:36.79

>>173
--(C)　　(D)------
|　|　＼／＼　　|
|　D---B ---D　　|
|　|　／＼／　　　|　
--(A)　　 C--(A)--

ほらね、５色目が必要でしょ。

**１３２人目の素数さん** · 2011/04/03(日) 16:37:24.77

>>174
　直感的に反例があるのは分かっていたが、そういう示し方があったのね。
　>>128の方法と同様の方法で、ケンプ鎖を使わずに5色定理が示せるので
　最後の部分を除いて気に入っています(ケンプ鎖は個人的に嫌いなので)。

よければ、>>147-163も見てやってくださいな・・・・

**１３２人目の素数さん** · 2011/04/03(日) 17:34:22.05

>>176
何度も言っているけど, たとえ >>176 のグラフを
塗り分けるのに5色目が必要であるとしても,
だから何だというの?

例えると
(1) あなたが,　ある推論の下に
「このグループのメンバーは全員が男である」
と主張をした.

(2) 私はグループから一人選んで「でも, この人は女ですよ.
あなたの主張は間違いです」といった.

(3) あなたは (2) とは別のメンバーを連れてきて
「女性であるのは特殊な場合のみ. この人は男だ」
といっている.

(2) で選んだメンバーを「女じゃない, 男でしょ」というなら
反論になるけどそうじゃなけりゃ, いくらメンバーから男を探して
連れてきても, (2) の段階で残念ながらあなたの推論と主張の
誤りは確定なんだよ.

**１３２人目の素数さん** · 2011/04/03(日) 19:29:48.06

>>178
中学生でもわかる論理を、何度言っても理解できない人に対して、
何度言っても無駄な事かと。
>>95 はある意味真実なので。

**帰納と類比** · 2011/04/03(日) 22:22:10.31

>>125-179
過去レス確認。
みんなケンペ鎖のことをよく理解してないな。
>>145
ＡＢチェーンの入れ替えＢＡチェーンにし、ＡＣがＢＣチェーンとなり
ＣのところにＢを置いて矛盾
>>170
ＢＣチェーンの入れ替えＣＢチェーンにし、ＡＣがＢＣチェーンになり
ＡのところにＢを置いて矛盾
>>173
ＡＤチェーンにＡのところにＤを置いて矛盾
接合の反対＝展開をしてメモでも取って図に書いて確認してください。

**１３２人目の素数さん** · 2011/04/03(日) 23:27:17.62

どういう理屈で何が何に矛盾してるのか書けよ

**１３２人目の素数さん** · 2011/04/04(月) 09:46:05.59

帰納と類比には論理的思考力がない典型例ってゆーか、
∃(ある)と∀(すべて)が絡むと理解不能に陥るようだね。

Ｐ「ある塗分け方で４彩色不可能」
Ｑ「すべての塗分け方で４彩色不可能」

Ｑは反例を一つ示せば主張は崩れるのであって、
それに対抗してＰの例をいくら挙げてもＱの不成立には変わりない。

帰納と類比の脳内では∃と∀がゴッチャになってるから、
いつまでも基本的な誤解に気付かず、周りの話が飲み込めない。

こんなの論理学の初歩なんだけどね。
「∃と∀の区別なんかはどうでもいい」って思ってるだろ？
それが致命的欠陥なんだよ。

**１３２人目の素数さん** · 2011/04/04(月) 20:51:05.52

>>181
たしかに、帰納と類比に、「どういう理屈で」「何が」「何に」矛盾しているのか
書かせてみると面白そう。

**１３２人目の素数さん** · 2011/04/04(月) 23:11:44.08

そんなの聞いてもどうせ、「>>6を読んでください」「考察してください」しか言わないだろ。

**１３２人目の素数さん** · 2011/04/04(月) 23:52:00.74

というか>>174も

┌─────┬─────┐
│　　　 A 　　│　　B　　　　 │
│　 ┌─┬─┴─┬─┐　 │
│　 │ 　│　　　　│　 │　 │
│　 │Ｂ │ 　C　 │A│　　│
│　 │ 　│　　　　 │　 │　 │
│　 │ 　├───┤　 │　 │
│　 │ 　│　　D　│　 │　　│
│　 │ 　├─┬─┤　 │ 　│
│　 │ 　│A │B│　 │ 　 │
│　 │ 　├─┴─┤　 │ 　│
│　 │　 │　 C 　│　 │　　│
│　 └─┴┐ 　┌┴─┘ 　│
└────┴─┴────┘
ときちんと四色で塗り分けられるが(当たり前だが)

**帰納と類比** · 2011/04/05(火) 05:26:40.60

>>182
Ｎ－２点の相対グラフである塗分け方で４彩色不可能
であるが、帰納法の仮定に矛盾するので矛盾を引き起こす
配色は存在しないと結論付けている。
このある塗り分け方を矛盾としたら、Ｎ点の相対グラフは
全て４配色可能であると結論付けられる。
この反例を矛盾としたことに帰納法の証明になんの問題もないと思うが。
ごく一般的な証明であると思う。

**１３２人目の素数さん** · 2011/04/05(火) 10:58:56.75

>>186
2行目の「帰納法の仮定」は何？
1行目とどう矛盾する？
具体的に書けよ

**１３２人目の素数さん** · 2011/04/05(火) 21:11:37.47

>>186
簡単に答えられる質問です。

「Ｎ－１点までのグラフは４配色可能であると仮定する。」
1. この仮定したグラフを四色で塗り分ける方法は何通り(以上 or 以下)あるか？
2. この仮定したグラフを五色で塗り分ける方法は何通り(以上 or 以下)あるか？
3. この仮定したグラフのいくつかの頂点の彩色を指定することで、
　　四色で塗り分けられないようにできるか？

4. 「接合」して得られたグラフを四色で塗り分ける方法は何通り(以上 or 以下)あるか？
5. 「接合」して得られたグラフを五色で塗り分ける方法は何通り(以上 or 以下)あるか？
6. 「接合」して得られたグラフのいくつかの頂点の彩色を指定することで、
　　四色で塗り分けられないようにできるか？

7. 1～3の答えと4～6の答えで矛盾することがあるか？

**帰納と類比** · 2011/04/05(火) 21:59:10.50

>>188
Ｎ－１点以下の相対グラフはわかるが、Ｎ，Ｎ－１，Ｎ-２，Ｎ－３・・・・
点のどの相対グラフか分からないので答えようがない。
１～３はＮ－１点か
４～６はＮ－２点か
よく分かりません。

**１３２人目の素数さん** · 2011/04/05(火) 22:24:48.96

>>187 にも答えてもらえませんか？ > 帰納と類比

**188** · 2011/04/05(火) 22:56:32.17

>>189
Ｎに具体的な値を与えて、適当な大きさのグラフを想定してくれれば良いです。
1. 一通り以上。というのは良いですよね？
3.と6.はできる or できないで答えてください。

**帰納と類比** · 2011/04/05(火) 23:40:48.36

>>187
帰納法の仮定：Ｎ-１点までは４配色可能である。
Ｎ－２で５色目が必要になる。これが仮定と反する。
>>188,>>191
1.１つ以上
2．１２個以上
3．できない
4．１つ以上
5．１２個以上
6．最終的に帰納法の仮定から言って、できない
7．最終的に矛盾はない

**１３２人目の素数さん** · 2011/04/05(火) 23:45:42.90

>>146で「検討してみます」と言った結果が>>165 >>170 >>176なのかな？
自分で考える気になったのはすごい進歩だと思ったのだが…

**１３２人目の素数さん** · 2011/04/06(水) 00:18:26.94

>>192
とりあえず >>187 に答えてくれてありがとう。

では、「Ｎ－２点の相対グラフがある塗分け方で
４彩色不可能」であることが、
「Ｎ-１点までは４配色可能である」に矛盾すると
あなたは考えてるんだね。

ちなみに「N-1 点までの(任意の)グラフは4配色可能である」
の否定は

「N-1 点までの点をもつ、あるグラフは頂点をどのように
4色で塗っても塗り分けられない」

であることには同意してもらえるかな？

**帰納と類比** · 2011/04/06(水) 00:30:40.56

>>194
同意します。

**１３２人目の素数さん** · 2011/04/06(水) 01:21:41.03

>>195
そこは同意してもらえるんだね。

では、あなたの証明とかその状況は忘れてください。
以下を全く一般の話として読んで下さい:

あるグラフが与えられたとしよう。

(1) 「そのグラフは、ある塗り方で頂点を 4色で塗ると塗り分けられない」

(2) 「そのグラフは、どのように頂点を 4色で塗っても塗り分けられない」

一般には (2) ⇒ (1) が成立するが, (1) ⇒ (2) は成立しない。
(1) と (2) は異なる主張である。

以上、同意してもらえますか？

**１３２人目の素数さん** · 2011/04/06(水) 06:02:37.31

帰納と類比さー
>>192
で、「N-1 で 5色目が必要になる。」って書いているけど、
四色定理によれば、そんなことは起こり得ないんだけどｗｗｗ

つまり、特殊な条件のもとでは N-2 （？帰納と類比の話によれば、N-1の筈だが・・・（苦笑））
で 5色目が必要になるって言いたいんでしょ。

で、「帰納法の仮定：N-1点まではどんなグラフでも4配色可能である。」
と、どこがどう反するのさｗｗ

ちゃんと高校卒業したか？

**帰納と類比** · 2011/04/06(水) 06:07:57.11

>>196
同意します。

**１３２人目の素数さん** · 2011/04/06(水) 10:38:05.34

>>198
そこも同意していただけますか。

では、>>192 によれば

>>帰納法の仮定：Ｎ-１点までは４配色可能である。

ですね。この「帰納法の仮定」の否定は
(a) 「N-1点までのあるグラフはどのように頂点を塗っても4色で
塗り分けられない」　
です (>>195 で同意済)。

(b) 「N-2点の双対グラフがある塗り方で頂点を 4色で塗ると塗り分けられない」
ことから、上で述べた(帰納法の仮定の否定である) (a) は「一般には」導かれません
(>>198 で同意済)。

いいかえると、(b) は帰納法の仮定と、「一般には」矛盾しません。

ですから >>186 の冒頭2行を読んで考えられるのは次の二つです。
(A) 説明不十分。「帰納法の仮定と矛盾する」根拠が他にある
(B) 冒頭2行の推論が間違っている

どちらですか？
(A) ならば、説明不十分なのだから追加説明もお願いします。

**188** · 2011/04/06(水) 21:25:26.63

>>192
解答ありがとうございます。

4～6の所では背理法を適用せず、7.の所で背理法を使うようにすると
6．最終的に帰納法の仮定から言って、できない、
7．最終的に矛盾はない。
を以下のように書き換えるのは納得してもらえますか？
6. できる、
7. (3.と6.の答えが異なるので)矛盾する。(この後矛盾を解消する。)

3.はできないとの解答ですが、2.の解答と矛盾します。
2.の解答より五色で塗り分ける方法が存在すると言ってます。
「5集点は不可避集合である」ことから、五色で塗り分ける方法のどれかを選んで
いくつかの頂点の彩色を指定すれば、3.の場合も四色で塗り分けられないように
できるのは理解できますよね？
6.の場合に同様の考え方をしているはずです。

用意していた解答は、1～2と4～5は一通り以上、
3.と6.はできる、
7. (1～3の答えと4～6の答えは同じなので)矛盾しない、
(よって、多くの人も書き込んでいたように帰納法の仮定と矛盾しない。)
でした。