各位好
想問一下大神有沒有這些證明的頭緒

這裡的k(G)是指 : The size of the 「smallest」 vertex cut
謝謝

第一題 寫得潦草 有錯提醒一下 https://i.imgur.com/bPrw7iJ.jpghttps://i.imgur.com/KSEOntB.jpg

修網址 https://i.imgur.com/bPrw7iJ.jpg

抱歉 匆忙看錯題目這才對 https://i.imgur.com/iFN3s3M.jpg更正 https://i.imgur.com/x3JxrRf.jpg抱歉啊 寫錯一直改

G不是connect，不能帶e<=3v-6 而且應該是3/2v<=e<=3v-6

G應該是connect 不然題目不會給min vertex cut=5

因為是k(G)=5 所以一定是connect 且每點degree 至少為5

抱歉～沒看清楚，直覺以為那代表components個數

請問c大為什麼每個點的degree至少為5？

如果有一點deg<=4 那把他連出去的vertex都拿掉即形成一個cut 與題目條件矛盾 所以一定>=5

對齁，感謝anonimo !請問 G的補集中，為什麼deg(v)=6 ?喔~ 我知道了，是因為sum的deg(v) = 2e = 2*C12取22*12*11/2=132，132-60=72(補集)，72/12=6=deg(v)

可以這樣想 總node為12則每點最多11邊 G有5邊 那補圖就是6了

c大這個方法更好! 謝謝!