各位好
想问一下大神有没有这些证明的头绪
https://imgur.com/a/d5wUNhM
https://imgur.com/a/uuizLKh
这里的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大这个方法更好! 谢谢!