设G(p,q)是简单图.δ(G)>=|p/2|,则G必连通.怎么证明?这是刘任任老师离散书上的定理,不过看不懂“G的每个分支至少有_数学解答

设G(p,q)是简单图.δ(G)>=|p/2|,则G必连通.怎么证明?
这是刘任任老师离散书上的定理,不过看不懂“G的每个分支至少有|P/2|+1个顶点”这部分,

人气：387 ℃　时间：2020-06-13 09:18:12

解答

对于G的任何一个分支,从中任选一个点,然后把和它相连的点(δ(G)>=|p/2| => 至少|p/2|个和它相连的点)算在一块就有|P/2|+1个点了,所以这个分支里至少有|P/2|+1个顶点.
所以G的每个分支至少有|P/2|+1个顶点.