证明如下序列不可能是某个简单图的次的序列： （1)7 6 5 4 3 2。（2)6 6 5 4 3 2 1。（3)6 5 5 4 3 2 1。
序列
已帮助 人
证明如下序列不可能是某个简单图的次的序列：
(1)7,6,5,4,3,2。(2)6,6,5,4,3,2,1。(3)6,5,5,4,3,2,1。
-
证 (1)已知定理1：
而在此序列中，∑d(v)=27，为奇数，所以此序列不可能为图的次的序列。
又知定理2：奇点的个数应为偶数，而在此序列中，奇点7、5、3为奇数个，所以此序列不可能为图的次的序列。
(2)此序列中，奇点5、3、1为奇数个，所以此序列不可能为图的次的序列。
(3)对于7顶点的图，假定
d(v1)=6，d(v2)=5，d(v3)=5，d(v4)=4，d(v5)=3，d(v6)=2，d(v7)=1
并假设G为简单图，则v1存在与其它六个点的连线(包含与v7)；v2与v1间存在边e12，而v7次为1，所以必不与v1外的其它点相连，因而v2与除v1，v7外的四点间各有一连线。
假设G(V，E)为简单图，则余下的v3，v4，v5中任一点(用vi表示)已确定存在ei1，ei2，无ei7，对于d(vi)=5的该点来说，必与除v7外的每一点都有连线，设d(v3)=5。
由此推论，v4，v5，v6都同时与v1，v2，v3相连，即v4，v5，v6的次至少是3，这与d(v6)=2相矛盾。
故假设不成立，该图中可能有环或多重边，非简单图的次的序列。