企源知识库

设图G有n个结点，n+1条边，证明：G中至少有一个结点度数≥3。
【正确答案】：

显然发生矛盾，不可能每个结点度数小于等于2，即至少有一结点度数≥3。