企源知识库

已知n阶无向图G中有m条边，每个结点的度数不是k就是k+1。证明：G中k度结点的个数为n(k+1)—2m。
【正确答案】：证明：设G中k度结点的个数为x，那么,k+1度结点的个数为n-x。由结点度数总和等于边数的两倍，得2m=kx+(k+1)(n一x),x=n(k+1)—2m。