Question

求解离散数学题目：

假设一条带有m条边，n个顶点的连通平面性简单图不包含长度不大于3回路。证明：则m小于等于2n-4

Answer 1

设这个图有k个面。
定义deg(Ri)是第i个面的次数，即这个面的边界长度。
则一定有∑deg(Ri) = 2m （对所有面的边界长度求和，相当于把每一条边算了两次）
在本题里，∑deg(Ri) >= 4k （因为每个面至少是由四条边围成）
所以2m>=4k, 即2k<=m
根据欧拉公式：n+k-m=2
可得 4=2n+2k-2m<=2n+m-2m=2n-m
即m<=2n-4