证明:每个面至少有4条边围成的任何连通简单平面图中,m≤2n-4,其中n为顶点数,m为边数。

证明:每个面至少有4条边围成的任何连通简单平面图中,m≤2n-4,其中n为顶点数,m为边数。
【正确答案】：证明:设图有m条边,n个顶点,r个面。
由已知,4r≤2m,r≤m/2。
简单平面图满足欧拉公式,n-m+r=2,
2=n-m+r≤n-m+m/2=n-m/2,整理得,2n-m≥4,m≤2n-4。证毕

↑

证明:每个面至少有4条边围成的任何连通简单平面图中,m≤2n-4,其中n为顶点数,m为边数。

相关题目