图论证明题

问题描述:

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

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