1) ( 3,3,2,3 ),( 5,2,3,1,4 )能成为图的度数序
列吗?为什么?
2) 已知图 G 中有 10 条边, 4 个度数为 3 的结点,其
余结点的度数均小于等于 2 ,问 G 中至少有多少
个结点?为什么?
度数序列
解 1 )由于这两个序列中,度数为奇数的结点个数均为奇数,由握手定理的推论知,它们都不能成为图的度数序列。
2 )图中边数为10 ,由握手定理知, G中所有结点的度数之和为20 ,4 个度数为3 的结点占去 12度,还剩下 8度。若其余全是度数为2 的结点,还需要4个结点来占用这8 度,所以G至少有 8个结点。
第 4 页 / 共 23 页