[理工] 105 台大電機 離散

[lwlt1995 (seyaku)]

板上的各位強者大家好
我想問第四題的C選項和第六題(黃色螢光筆處)

http://i.imgur.com/GEuolSX.jpg

第4題的C是是非題
第六題是證明題
這兩題腦袋打結
想不到有什麼做法

跪求強者提點小弟orz

-----
Sent from JPTT on my Sony D6653.

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.248.97.151
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1484583047.A.E4E.html
※ 編輯: lwlt1995 (111.248.97.151), 01/17/2017 00:11:48
→ AkariAkaza: 4-c p=11,q=2
→ lwlt1995: 感謝你 昨天想了超久想不到囧
→ aa06697: c就腦力激盪... p=3 q=2
→ aa06697: 最後一題我是假設connected (我看補習班老師好像也是假設
→ aa06697: connected)
→ aa06697: connected planar => e<= 3v-6 => 2e <= 42 又2e = degre
→ aa06697: e和 = 9d 所以d<=4 補圖之d' >= 9-4 = 5 因為所有點degre
→ aa06697: e >= n/2 所以有HC (此為另一個定理推過來的：任兩不相鄰
→ aa06697: 點degree和為n則有HC)
推 aa06697: 想一想應該是可以假設connected 因為他是說prove or disp
→ aa06697: rove 大不了分個case2 不connected 則不會有HC
推 yorunohoshi: http://i.imgur.com/yRls3BR.jpg   我是這樣寫@@
→ lwlt1995: 謝謝aa大跟yoru大的回答！
推 hearwhite: yoru大第四行 K5本來就都有四個邊，如果是connected應
推 hearwhite: 該不會扣掉頂點數還維持四個邊
→ hearwhite: aa大 d'=8-4=4才對
→ nctudada: 9個點 怎麼可能每個點的degree都是3 這樣總degree是奇
→ nctudada: 數欸