问答题
设G是简单平面图,证明:它一定有一个度数不大于5的结点.
【正确答案】
不妨设G是连通的.若不连通,就可考察G中的一个连通分支.因G是简单图,每个面至少有3条边,所以3r≤2e,即有r≤≤2e/3.
如果每个结点的度数都不小于6,则6v≤2e,即有v≤e/3.
由欧拉公式可得
2=v-e+r≤e/3-e+2e/3=0.
与题设矛盾,所以,G中至少有一个结点的度数不大于5.
【答案解析】
提交答案
关闭