企源知识库

设无向图G有7个顶点，每个顶点的度数不是4就是5。证明：G中至少有5个度数为4的顶点或至少有4个度数为5的顶点。
【正确答案】：(1)如果G中度数为4的顶点至少5个,则结论成立
(2)假设G中度数为4的顶点最多4个。
由于G有7个顶点且每个顶点的度数不是4就是5,所以G这时至少有3个度数为5的顶点。
由于一个图中度数为奇数的顶点的个数是偶数,
因此G这时至少有4个度数为5的顶点,结论仍成立。
(3)综合(1)和(2),结论成立。