avril4ever
幼苗
共回答了24个问题采纳率:87.5% 举报
反之若不连通,设此图可以分成不连通的两部分,分别有a个和n-a个顶点,则这个图边数最多不会超过a(a-1)/2+(n-a)(n-a-1)/2条(也就是两部分都是完全图).可以用不等式验证这个数小于等于1/2(n-1)(n-2),与已知m>=1/2(n-1)(n-2)+1矛盾.所以必连通
1年前
追问
2
举报
avril4ever
上面有个细节错了,应该是“可以用不等式验证这个数小于等于1/2(n-1)(n-2) “ 简单的说,思路就是如果一个图能分成两个不连通的部分的话,边数最多的情况是两个图都是完全图。而即使两部分都是完全图,边数也不会超过1/2(n-1)(n-2)+1,边最多的情况是1个单点和一个n-1阶完全图的时候