Re: [圖論] 三角形, 補圖, NPC

[XII (Mathkid)]

※ 引述《wsx02 ()》之銘言：
: 1&2. http://ppt.cc/xPZh
: 請問有人知道這兩題該怎麼證嗎?

1.

設六點為a,b,c,d,e,f, 則ab,ac,ad,ae,af中必有三邊同色,可設ab,ac,ad為藍色.

若bc,bd,cd中有一邊為藍色, 則有藍色的三角形.

若bc,bd,cd均為紅色, 則有紅色的三角形.

故必有單色三角形, 可設abc為藍色三角形.

若d連出3個藍邊, 則有非abc的藍三角形或紅三角形.

若d連出3個紅邊, 且da,db,dc並非均為紅邊, 則有含d的紅三角形或非abc的藍三角形.

故可設a,b,c與d,e,f之間均以紅邊相連, 則有非abc的藍三角形或紅三角形.

2.

找邊數較多的那一個圖, 則 e ≧ C(n,2)/2 = n(n-1)/4.

當 n≧11 時, 若此圖為平面圖, 則 2e≧3f.

由Euler公式,

2 ≦ n-e+f ≦ n-e/3 ≦ n-n(n-1)/12 = n(13-n)/12 < 2, 矛盾.

故此圖不為平面圖.

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.166.204.109
推 wsx02       :原來1.是6人必3人相識或不相識的鴿籠@@
→ wsx02       :可是這樣是證出有一個同色的三角形嗎?
→ wsx02       :題目說要證2個同色的三角形 證出1個同色有部分分數
→ wsx02       :請問有辦法證出兩個同色的三角形嗎? 謝謝!
→ XII         :我看錯題目..
※ 編輯: XII             來自: 118.166.204.109      (10/20 22:34)
推 wsx02       :請問若 d連出3個藍邊, 則有非abc的藍三角形或紅三角
→ wsx02       :最差的情況是de,df為藍  另一條設dc為藍
→ wsx02       :我畫的圖是 http://ppt.cc/qVN2
→ wsx02       :請問我有什麼地方誤會嗎? 謝謝
推 wsx02       :我從我畫的圖 一直延伸下去 可以有找到2個同色三角
→ wsx02       :只是步驟變得有點繁雜..
→ XII         :會有紅CEF或藍DCE或藍DCF或藍DEF
→ sneak       : 題目說要證2個同色的三 https://muxiv.com
→ sneak       : 最差的情況是de,df https://daxiv.com