图论证明题

分类: 作业答案 • 2022-09-24 20:29:26

问题描述：

图论证明题
设9阶无向图的每个顶点的度数为5或6,证明它至少有5个6度顶点或者至少有6个5度顶点.

答

设有a个6度点,则有9-a个5度点,6a+5（9-a）=2倍的边数,故a为奇数,a至少有6个5度顶点