企源知识库

设G是有n个结点、n+1条边的简单连通图，且G中存在度数为5的结点证明：G中至少有一个度数为l的结点。
【正确答案】：证明：假设C中不存在度数为I的结点，由于G是连通图，所以G的每个结点的度数≥2。
G有n个结点，且有一个度数为5的结点，所以C的结点度数总和至少为2（n-1）+6元2n +3。
另一方面，由于G有n + 1条边，所以G的结点度数总和为2n +2。
而2n+2≥2n+3是不可能的，因此假设为谬。所以G中至少有一个度数为1的结点。