设G为9阶无向图，每个结点度数不是5就是6，则G中至少有 （ ） 个5 度结点。

设G中有n个5度结点，则有9-n个6度结点。因为每个结点的度数只能是5或6，所以G中总共有 $5n+6(9-n)=54-n$ 条边。根据握手定理，G中边数应该是所有结点的度数之和的一半，即 $\frac{1}{2}\sum_{v\in G} d(v)$。由于每个结点的度数都不是5就是6，所以 $\sum_{v\in G} d(v)$ 必定是偶数。因此，$5n+6(9-n)=54-n$ 必须是偶数，解得 $n\geq 3$。因此，G中至少有3个5度结点。

相关问题

2设口阶圈G中有m 条边，每个结点的度数不是k的是k+1，若G中有小个k度顶点：Nos 个k+1度顶点，则NK=

根据握手定理，对于一个无向图 G，其所有顶点的度数之和等于 2m，其中 m 为边数。设 G 中有 n 个顶点，则有以下方程成立：

n*k + Nos*(k-1) + NK*(k+1) = 2m

又因为 G 中有 NK 个 k 度顶点和 Nos 个 k+1 度顶点，所以 n = NK + Nos，代入上式得：

(NK + Nos)*k + Nos*(k-1) + NK*(k+1) = 2m

化简得：

NK = (2m - k*Nos)/(k+1)

因此，NK 的值为 (2m - k*Nos)/(k+1)。

一个含4个结点的无向图中有3个结点的度数分别为1，2，3，则第4个结点的度数不可能是

第4个结点的度数不可能是2。因为如果第4个结点的度数为2，则这个图可以看作是由一条边和两个有度数3的结点组成的，这样就无法满足第1个结点的度数为1的条件。同样地，第4个结点的度数也不可能是3，因为如果第4个结点的度数为3，则这个图可以看作是由一个三角形和一个度数为1的结点组成的，这样就无法满足第2个结点的度数为2的条件。因此，第4个结点的度数只能是0或4。