精选优质文档-倾情为你奉上习题10 1.(1)图G的度数列为2、2、3、3、4，则G的边数是多少？(2)3、3、2、3和5、2、3、1、4能成为图的度数列吗？为什么？(3)图G有12条边，度数为3的结点有6个，其余结点的度数均小于3，问图G中至多有几个结点？为什么？解 (1)设G有m条边，由握手定理得2m2233414，所以G的边数7条。(2)由于这两个序列中有奇数个是奇数，由握手定理的推论知，它们都不能成为图的度数列。(3) 由握手定理得2m24，度数为3的结点有6个占去18度，还有6度由其它结点占有，其余结点的度数可为0、1、2，当均为2时所用结点数最少，所以应由3个结点占有这6度，即图G中至多有9个结点。2.若有n个人，每个人恰有3个朋友，则n必为偶数。证明 设、表示任给的n个人，以、为结点，当且仅当两人为朋友时其对应的结点之间连一条边，这样得到一个简单图G。由握手定理知3n必为偶数，从而n必为偶数。3.判断下列各非负整数列哪些是可图化的？哪些是可简单图化的？(1)(1，1，1，2，3)
