设G(p,q)是简单图.δ(G)>=|p/2|,则G必连通.怎么证明?
问题描述：
设G(p,q)是简单图.δ(G)>=|p/2|,则G必连通.怎么证明?
这是刘任任老师离散书上的定理,不过看不懂“G的每个分支至少有|P/2|+1个顶点”这部分,
答
对于G的任何一个分支,从中任选一个点,然后把和它相连的点(δ(G)>=|p/2| => 至少|p/2|个和它相连的点)算在一块就有|P/2|+1个点了,所以这个分支里至少有|P/2|+1个顶点.
所以G的每个分支至少有|P/2|+1个顶点.