[離散] 圖論 Hamilton cycle

[ken1325 (優質水瓶男)]

G=(V,E), |V|=n
若G中任二個不相鄰的點 x,y
滿足 deg(x)+deg(y)>=n
則G具Hamilton cycle


所以G如果沒有Hamilton cycle
deg(x)+deg(y)一定<n嗎？


--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 220.136.74.227
推 Sumboy      :可能會存在二點會是這能吧
→ Sumboy      :　　　　　　　　　　樣
→ nendi       :一定會存在兩個定點x,y使得deg(x)+deg(y) < n
→ ken1325     :thx