[理工] 離散 交大101 圖論

[clonsey1314 (Clonsey)]

What is the largest n so that the following assertion is always true?
Assertion:
Let G be a graph with 10 vertices in which there is at least one edge among
any three vertices. Then G must contain Kn, where Kn is the complete graph
with n vertices.


https://imgur.com/DEt2zUs
https://imgur.com/p8QrQcg

請問為甚麼解答一開始就這麼確定是K4, 然後就直接證是K4?
是要先用猜的嗎? 還是有甚麼方法可以直接先判斷是K4?

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 1.161.228.154
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1513429239.A.DA6.html

※ 編輯: clonsey1314 (1.161.228.154), 12/16/2017 21:01:46
→ TMDTMD2487: 我把它當作六個人必有三個人相認識或不互相認識的題目
→ TMDTMD2487: 的一個延伸
→ TMDTMD2487: 與x相鄰的六個點必定有三個點連滿或都沒有連
→ TMDTMD2487: 都沒有連的話與題意不合所以會有三個連滿的點
→ TMDTMD2487: 我想步道別的方法XD
→ TMDTMD2487: 解答一開始取deg(x)<=5 就是為了製造上面的情境我想
→ TMDTMD2487: 10個點再擴大我猜也是這種方法做下去
→ clonsey1314: 為什麼這麼肯定的取6個?
推 sarsman: 這題我覺得交大超狠的，題目量已經多到很難做完了還出這
→ sarsman: 種題目XDD
→ sarsman: 三點必有一邊，所以固定一點x考慮，與x不相連的點必能形
→ sarsman: 成complete subgraph
推 TMDTMD2487: 上述只有證明他前半部分講得@@
→ TMDTMD2487: 六個就只是為了把那個很基本的題目延伸過來而已(六個
→ TMDTMD2487: 人的那個
→ TMDTMD2487: 不用擔心這種東西交大應該考一次就換題目了