设G是有p个顶点q条边的（简单)无向图 且G中每个顶点的度数不是k就是k＋1 则G中度为k的顶点的个
顶点,度数
已帮助 人
设G是有p个顶点q条边的(简单)无向图，且G中每个顶点的度数不是k就是k+1，则G中度为k的顶点的个数是多少()。
A、p/2
B、p(k+1)-2q
C、pk
D、p(p+1)
-
参考答案：B。
参考解析：因为顶点度数只有两种，所以设k度的顶点数为x，k+1的为(p-x)，又因为是无向图，所以顶点数乘以相应度数之和为图中边数的2倍(一条边代表一次入和一次出)，所以kx+(k+1)(p-x)=2q，解得x=p(k+1)-2q，选择B。