Question

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

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

Answer 1

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