[其他] 請問有人會漢米爾頓路徑嗎？

[littlejumi (____)]

對圖 G=(V,E)而言，若任意兩定點u,v均可保證deg(u)+deg(v)>=n-1 ,則G必有漢米爾頓路
徑（Hint ,在G外面另取一點連到G中的所有頂點）


拜託幫幫我一下 ，這題有問題？

--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 223.136.57.195
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1435825550.A.B17.html
推 XII         : Ore theorem
推 softseaweed : ore不是只保證 >= n
推 kerwinhui   : 如題，加一點*後 deg(u)+deg(v)>=#(V union {*})
→ kerwinhui   : 所以有Hamiltonian cycle，把*拿掉得path
→ littlejumi  : 想再清楚一點的算式 有點不是很懂耶。有完整的證明
→ littlejumi  : 嗎？
推 LeeMY       : 手邊的證明寫的超級長…
→ kerwinhui   : 明明就已經寫完…