证明:每个面至少有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。  证毕