设无向图G有7个顶点，每个顶点的度数不是4就是5。证明：G中至少

设无向图G有7个顶点，每个顶点的度数不是4就是5。证明：G中至少有5个度数为4的顶点或至少有4个度数为5的顶点。
【正确答案】：

设图G中度数为4的顶点有x个，则度数为5的顶点有7-x个。又设图G的边数为e。由握手定理，得方程：4x+5(7-x)=2e即35-x=2ex=35-2e由此可见，x必为1到7之间的奇数。下表列出了所有的可能。由表可以看出，G中至少有5个度数为4的顶点或至少有4个度数为5的顶点。