企源知识库

设图G有n个结点，n条边，且存在度数为1的结点。
证明：G中至少有一个结点度数≥3。
【正确答案】：假设G中不存在度数≥3的结点，则C的每个结点的度数最多为2。（2分）
G有n个结点，且有一个度数为1的结点，所以G的结点度数总和最多为2（n-1）+1= 2n-1。
另一方面，由于G有n条边，所以C的结点度数总和为2n。（2分）
而2n≤2n-1是不可能的，因此假设为谬。所以G中存在度数≥3的结点。（1分）