离散数学图论证明设九阶无向图G.每个顶点度数不是五就是六,证明至少有五个六度顶点或六个五度顶点.
问题描述：
离散数学图论证明
设九阶无向图G.每个顶点度数不是五就是六,证明至少有五个六度顶点或六个五度顶点.
答
反证法
设G最多有4个六度且最多有5个五度,又因为奇度的顶点为偶数个,显然G最多有4个五度顶点和4个六度顶点,与九阶无向图矛盾