设图G中至少有9个结点每个结点的次数不是5就是6 试证G中至少有5个6次结点或至少有6个5次结点．

大学 2020-01-22 01:00:15 结点,次数,不是已帮助人

设图G中至少有9个结点，每个结点的次数不是5就是6，试证G中至少有5个6次结点或至少有6个5次结点．

难度★★☆ 搜索

证明根据图论中定理，任何图中奇结点数为偶数，因此5度结点的个数只能为0，2，4，6，8；此时对应6度结点的个数则为9，7，5，3，1．对这5种情况都满足至少有5个6度或6个5度结点的情况，故结论成立．
本题条件是图G共有9个结点，每个结点的度数是5或是6．而要证明的是满足两种情况之一即可，对于5度结点至少为6个，即可以是6个或8个．而如果只有4个5度结点时，那么剩下9-4=5个结点，而这5个结点的度数为6(即至少有5个6度结点)．而如果只有0个、2个5度结点时，则对应有9个、7个6度结点，也满足至少5个的情况．同理，从至少5个6度结点出发，本题条件是图G共有9个结点，每个结点的度数是5或是6．而要证明的是满足两种情况之一即可，对于5度结点至少为6个，即可以是6个或8个．而如果只有4个5度结点时，那么剩下9-4=5个结点，而这5个结点的度数为6(即至少有5个6度结点)．而如果只有0个、2个5度结点时，则对应有9个、7个6度结点，也满足至少5个的情况．同理，从至少5个6度结点出发，少于5个或多于5个时的情况也能得出相应结论．

设图G中至少有9个结点 每个结点的次数不是5就是6 试证G中至少有5个6次结点或至少有6个5次结点．