[理工] [離散] 90交大

[linesx3 (小李)]

題目如下

4 An undirected graph G has n verties and all but one vertex of G

  are of odd degree.

  (a)What are the possible values of n ?

  (b)How many vertices of odd degree are there in the complement of G?

我的問題是:題目是指說在G中只有一個點的degree是odd嗎?但這不是不合圖論第一定裡嗎

           還是說這個英文是說除了一個點之外其他點都是odd degree啊,

           感覺英文好難喔!

           謝謝指教

--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.119.164.166
※ 編輯: linesx3         來自: 140.119.164.166      (03/10 11:26)
※ 編輯: linesx3         來自: 140.119.164.166      (03/10 11:27)
→ keepoo:除了一個點之外
→ keepoo:其實你發現不合定理的時候->沒辦法算->大膽用另一個想法吧
推 ianwuzack:除了一個點之外+1
→ gsrr:除了一個點外,其他點都是odd degree
→ EntHeEnd:請問這一題怎樣解呢 ?
推 bensome0624:(a)n is odd and n>1,這樣degree加起來才會是偶數
推 Lautreamont:這題要用偶、奇數相加減的結果是否為偶奇數的觀點解
→ keepoo:(a)n為odd    (b)邊數：完全G = G + G補
→ bensome0624:(b)n-1個,原本為奇數degree的點在這個補圖還是奇數
→ EntHeEnd:嗯嗯 感謝回答 我也知道是要奇數個 可是沒解答很不踏實..
→ bensome0624:講錯,(a)n=0也可以
→ bensome0624:      1
→ bensome0624:          1
→ keepoo:XD
→ EntHeEnd:(b)有什麼直觀一點的想法嗎 ? 雖然畫圖可以知道...
推 bensome0624:degree(v)+degree(v補)=n-1,n是odd的話,n-1就是even囉
→ EntHeEnd:嗯嗯 感謝樓上