设G是无向简单图，有11个结点，每个结点的度数均至少为5。证明:G是连通图。

设G是无向简单图，有11个结点，每个结点的度数均至少为5。证明:G是连通图。

设G=。并设其有k个连通分支。因为在G中每个结点度数至少为5，所以，其每个连通分支必至少包含6个结点，因而：|V|≥6k.而|V|=11，所以k≤11/6.因为k是正整数，故k=1.所以图G必是连通图。