离散证明:一个图包含2n个结点,每个结点的度数大于等于n的简单图是连通的

题目

离散证明:一个图包含2n个结点,每个结点的度数大于等于n的简单图是连通的
证明:一个图包含2n个结点,每个结点的度数大于等于n的简单图是连通的.

答案

假设不连通.有如下两种情况：
1.最小连通分量有n个结点：此时共两个连通分量,每个分量n个结点.对于任一点,它的度至多是n-1,矛盾.
2.最小连通分量小于n个结点：该分量中任一点的度不超过n,矛盾.