推 wsx02 :謝謝! 11/06 23:24
※ 引述《wsx02 ()》之銘言：
: 1. cube有9個點 http://ppt.cc/v5Zr
: 2. 完全圖 http://ppt.cc/y0Yk
: 3. 三維空間不共線 http://ppt.cc/o2NG
: 請問有人知道這三題怎麼解嗎?
: 謝謝
2.
設G的10個頂點為:
v_1,v_2,...,v_10
Part(1)(欲證G必包含K4):
----------------------------------------------------------
假設G沒有包含K4(欲導出有矛盾)
則:
(1)deg v_i≧6, i=,1,2...,10
(因為若有deg v≦5:
不妨設 v_1,v_2,v_3,v_4 與v之間沒有邊
由題知:(考慮 v,v_i,v_j, 其中1≦i<j≦4)
則 v_1,v_2,v_3,v_4 兩兩之間必有邊!
G包含K4, 矛盾!)
(2)
由(1):
可設v_7 與 v_1,v_2,...,v_6中間均有邊
因為G沒有包含K4,所以
v_1,v_2,...,v_6中任挑3個頂點出來,這三個頂點間必至少有一個沒有邊--------(*)
考慮子圖G'=(V',E')
其中V'={v_1,v_2,...,v_6} ,E'={e屬於E |e的頂點均在V'中}
則deg v_i≦2, i=,1,2...,6
G'
(若有 deg v≧3
G'
不妨設v_1,v_2,v_3與v中間均有邊
由題知:(考慮 v_1,v_2,v_3)
不妨設v_1,v_2中間有邊
則v7,v,v_1,v_2兩兩之間必有邊! G包含K4, 矛盾!)
因為deg v_i≦2, i=,1,2...,6
G'
所以不妨設
v_1與v_2,v_3,v_4均沒有邊
由題知:(考慮 v_1,v_i,v_j, 其中2≦i<j≦4)
則v_2,v_3,v_4 兩兩之間必有邊!
與(*)矛盾!
綜何(1),(2)原圖G必包含K4!
Part(2)(存在符合原題條件,但G不包含K5)
----------------------------------------------------------
令G的補圖H為:五角柱 如下圖:
v_1
v_5 v_2
v_4 v_3
v_6
v_10 v_7
v_9 v_8
其中 v_1v_2 ,v_2v_3 ,v_3v_4 ,v_4v_5 ,v_5v_1
v_6v_7 ,v_7v_8 ,v_8v_9 ,v_9v_10 ,v_10v_6
v_1v_6 ,v_2v_7 ,v_3v_8 ,v_4v_9 ,v_5v_10
均有邊, 其餘的沒邊!
容易証明:G中不包含K5!
(反證法:
設a,b,c,d,e為K5
由對稱性:
不妨設a=v_1
則:b,c,d,e只能屬於{v_3,v_4,v_7,v_8,v_9,v_10}
b,c,d,e只能屬於{v_3,v_7,v_8}或{v4_,v_9,v_10}中
以A={v_3,v_7,v_8}∩{b,c,d,e} 和 B={v4_,v_9,v_10}∩{b,c,d,e}的個數討論:
A | B
-------
1 | 3
-------
2 | 2
-------
3 | 1
由圖知: |A|≠3,|B|≠3
因此|A|=2,|B|=2
又由圖知b,c,d,e只能為 v_3,v_7,v_4,v_10
但v_3,v_4沒有邊,矛盾!
所以G中不包含K5!
--
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.114.34.121