【正确答案】：证明:设G=
反证,若图中所有顶点的度数均大于4。
每个面至少由3条边组成 :3r≤2m<2×30=60,r<20,rmax=19。
图中各顶点度数之和为边数的2倍,∑deg(vi)=2m> 4n,即2n
平面图满足欧拉公式,n-m+r=2,m+2≤nmax+rmax=33,m≤31,mmax=31,矛盾。
证明:少于30条边的简单平面图有一个顶点度数小于等于4。
- 2024-08-04 00:08:37
- 离散数学(02324)
证明:少于30条边的简单平面图有一个顶点度数小于等于4。
【正确答案】：证明:设G= 为简单平面图,边数为m,顶点个数为n,面数为r。由已知,mmax=29。
反证,若图中所有顶点的度数均大于4。
每个面至少由3条边组成 :3r≤2m<2×30=60,r<20,rmax=19。
图中各顶点度数之和为边数的2倍,∑deg(vi)=2m> 4n,即2n得到n<15,nmax=14。
平面图满足欧拉公式,n-m+r=2,m+2≤nmax+rmax=33,m≤31,mmax=31,矛盾。
【正确答案】：证明:设G=
反证,若图中所有顶点的度数均大于4。
每个面至少由3条边组成 :3r≤2m<2×30=60,r<20,rmax=19。
图中各顶点度数之和为边数的2倍,∑deg(vi)=2m> 4n,即2n
平面图满足欧拉公式,n-m+r=2,m+2≤nmax+rmax=33,m≤31,mmax=31,矛盾。