经过找规律可以发现答案为 n−2n-2n−2 . 以下是证明： 令d[i]为 iii 的度数。 考虑一个点 iii 不被删去的条件，必然是前面与 iii 相邻的点 jjj（可以是多个）被删去，导致 d[i]d[i]d[i] 减小至小于等于 d[j]d[j]d[j] . 1)易知 ans!=nans!=nans!=n 。 2)考虑 ansansans 能否是 n−1n-1n−1 ，也就是只删一个点，设这个点为 iii 。 因为 iii 是唯一被删去的点，所以 d[i]d[i]d[i] 一定不是最大的，即 d[i]<n−1d[i]<n-1d[i]<n−1。 其次删去 iii 导致其余点的 d[]d[]d[] 均发生改变，从而无法被删去。 即 iii 和其余点都相连，d[i]=n−1d[i]=n-1d[i]=n−1 ，矛盾。 所以 ans!=n−1ans!=n-1ans!=n−1 . 3)我们可以构造出 ans=n−2ans=n-2ans=n−2 的情况： 构造完全图 GGG ,删去一条边 (i,j)( i,j)(i,j) 。这样 d[i]=d[j]=n−2d[i]=d[j]=n-2d[i]=d[j]=n−2 ,其余 d[]d[]d[] 均为 n−1n-1n−1 . 首先删去 VI,VjVI,VjVI,Vj ，这样其余点各少两条边，d[]d[]d[] 均变成 n−3n-3n−3 ,不用被删去。 由此 n−2n-2n−2 是合法的解，也是最大的解，所以答案就是 n−2n-2n−2 .