[理工] 離散 Hamilton cycle證明

[sevfouyu11 (sevfouyu11)]

https://i.imgur.com/pImgXOB.jpg

想請問定理6-10證明最後一行的與已知矛盾是和哪一項已知矛盾呢？

如果從原設“若G中無Hamilton cycle”證到最後一行“deg(a)+deg(b)<n”不是反而符合~q
→~p嗎

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 111.82.52.162 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Grad-ProbAsk/M.1598174298.A.E3E.html
※ 編輯: sevfouyu11 (111.82.52.162 臺灣), 08/23/2020 17:23:08
→ Ricestone: 跟"deg(x)+deg(y)>=n,for any 不相鄰的x,y"矛盾
→ Ricestone: 這句話是前提
意思是說“deg(x)+deg(y)>=n, for any x, y屬於V, x, y不相鄰”這個條件在它證明一開
始假設G中無Hamilton cycle時就要符合了是嗎？
※ 編輯: sevfouyu11 (111.82.52.162 臺灣), 08/23/2020 20:21:40
→ Ricestone: 是
→ Ricestone: 我們想從前提P推出結論Q，於是先假設~Q，證出一個跟P不
→ Ricestone: 相容的R，所以~Q是錯的   這邊要注意的是這個R不一定是
→ Ricestone: ~P，實際上這題"deg(a)+deg(b)<n"就不是~P了
那這樣我了解了，感謝你
另外想再請問一下這題~P的完整敘述是“存在相鄰的x, y屬於V, deg(x)+deg(y)<n”嗎？
※ 編輯: sevfouyu11 (111.82.52.162 臺灣), 08/23/2020 22:18:12
→ Ricestone: "存在不相鄰的x,y屬於V"
好  感謝
※ 編輯: sevfouyu11 (223.138.233.175 臺灣), 08/24/2020 14:49:04