[離散] 幾題hamiltion cycle

[xdd1524 (一個人的牙刷)]

a.設G=(V,E)是個連通且無方向性bipartie graph
頂點V分成m跟n個 ,試證當m跟n頂點個數不同,圖G沒有hamilton cycle?

我想法是,既然是bipartie graph,代表m跟n的點集合內各自不相連
所以要有cycle時,必定是m1→n1→m2→n2....→m1 這種情況
所行經過的路徑長必是偶數,hamilton cycle的頂點數又剛好等於邊數
故頂點數為偶數,因為bipartie graph的關係,2邊頂點數必定會相等.
但這只是想法,不能當證明,想不到要用什麼方法證明此題?


b.prove that if the graph G in part(a) has a hamilton path
then |m-n|=1 .

這題不太懂題意,是問G要是有hamilton path下,會有|m-n|=1的性質?


有人能指點一下嗎,thx

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 114.44.149.105
推 yusd24      :b. 的意思就是你講的那樣～如果有的話頂點數差 1
推 yusd24      :然後我覺得你的 a. 就已經是證明了= ="a
→ xdd1524     :這樣寫應該會被退回吧XD,第2題知道題意我還是不會證
→ xdd1524     :我想不到為啥hamilton path 頂點數會差1...
→ xdd1524     :hamilton cycle扣掉某一邊不就變成hamilton path
→ xdd1524     :所以根據題目a的結論,頂點數一樣應該可行的吧
推 plover      :P_n is bipartite graph but n could be even