可平面图一定是可平面图吗?
发布网友
发布时间：2024-07-21 14:03
共1个回答
热心网友
时间：2024-07-24 22:19
证明如下：
设G的边数为e1，点数为n，G的补的边数为e2，G和它的补的并的边数为 e。
e = n（n-1）/2 ,
假设G是可平面的，那么e1 <= 3n - 6 . e2 = e - e1 >= n(n-1)/2 - (3n-6).
如果G的补也是可平面的，那么 e2 <= 3n - 6.
则有 n(n-1)/2 - (3n-6) <= 3n -6 即 n2 -13n +24 <= 0.
由二次函数的性质我们可以知道当 n >=11 时， n2 -13n +24 > 0.
前后矛盾，所以G的补一定是非可平面的。
因为图和它的补图是互补的，也就是说一个非可平面的图的补图是可平面的。
