图论题,设G是有p顶点的图,δ(G)>=((p+k)-1)/2,试证：G是k-连通的.

Question

图论题,设G是有p顶点的图,δ(G)>=((p+k)-1)/2,试证：G是k-连通的.

Answer 1

按照k-连通的定义,只需要证明在G中删除任意k-1个顶点后,所得到的图仍是连通的.你自己可以验证一下,删掉k-1个点之后,所得到图的最小度≥（p-k+1）/2,这个新图的顶点数为p-k,显然是连通的.