企源知识库

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