设平面图G=是自对偶图,证明|E|=2(|V|-1)
时间: 2024-06-19 09:02:55 浏览: 204
偶图Kn,n-A(|A|=6)圈长分布的唯一性 (2007年)
设平面图G为自对偶图,即G的平面对偶图同构于G本身。由欧拉公式,有:
V - E + F = 2
其中V、E、F分别为G的顶点数、边数、面数。因为G是平面图,所以每个面都是由至少三条边围成的简单多边形,所以有:
3F ≤ 2E
同时,由于G是自对偶图,所以F=E/2。将上述两式代入欧拉公式中,得到:
V - E + E/2 ≤ 2
化简可得:
E ≤ 2(V - 1)
因此,证明了当G为自对偶图时,有|E|=2(|V|-1)。
阅读全文