完全图是平面图吗

在图论中，完全图是一种特殊的图形。它由 n 个顶点组成，并且每两个不同的顶点都有一条边相连。那么问题来了，完全图是不是平面图呢？

从定义上来看，平面图是指可以画在平面上的图形，使得所有边不相交。考虑完全图的一些性质，我们可以从以下几个角度来分析完全图是否为平面图。

1. 完全图的边数

由于完全图每两个顶点之间都存在一条边，因此完全图的边数为：m = n(n-1)/2。这个公式可以通过求解下图的方式得到：

​ O--------O

​ /|\ /|\

​ / | \ / | \

​ O--O--O--O--O--O

​ \ | / \ | /

​ \|/ \|/

​ O--------O

其中，n为顶点数量，m为边数量。

2. 图形的连通性

平面图必须是连通的，否则肯定不能画在同一个平面上。完全图最小也是 2 连通的，即任意删除一个顶点依然是连通图。

3. 欧拉公式

对于平面图G，它的顶点数v、边数e以及面数f 满足欧拉公式：v-e+f=2。证明如下：

- 假设平面图G只有一个无限大小的面，没有其他面。则显然 v-e+1=2，所以欧拉公式在这种情况下成立。

- 假设平面图G有多于一个大小限制的面。我们通过在图形中添加一些边和顶点，来构造一个等价的图形，使得添加的这些部分都是多边形（即所有顶点恰好是三角形或四边形）。这个操作不会影响欧拉公式的成立。同时，我们可以得到新图形的顶点数是否变化，边数和面数只是多了某些数量的三角形和四边形。令三角形的数量为t，四边形的数量为q，则：

v' = v + t + q

e' = e + 2t + 4q

f' = t + q + 1

把这些数值带到欧拉公式中，得到：

v' - e' + f' = (v + t + q) - (e + 2t + 4q) + (t + q + 1) = v - e + f + 2 = 4

综上所述，完全图不是平面图。原因在于完全图的边数随着顶点数增加得非常快，使得它无法被画在同一个平面上，使所有的边不相交。此外，从欧拉公式的角度来看，完全图的面数无限增长。正如我们已经证明的那样，欧拉公式只适用于大小受限的平面图。

不仅如此，对于完全图K5和K3,3进行的 Konigsberg 桥问题的变形也说明了完全图不是平面图。在 Konigsberg 桥问题中，希望能够找到一个路径，穿过问题中所有的桥，但同时不走重复的道路。通过将 Konigsberg 桥问题变形，我们可以得到如下图所示的问题：

O---O O O

| / | |\ /|

O---O---O O-O-O-O-O

| \ | |/ \|

O---O O O

如你所见，这个问题实际上是将两个连通的平面图进行了粘贴。通过 Konigsberg 桥问题的证明可知，所有连通的平面图最多拥有两个奇数度顶点。由于完全图是由 n 个点组成，其中奇数度顶点数量必定为偶数，因此完全图无法被划分为两个连通的平面图，因此也不是平面图。

在实践中，完全图往往由于其特殊的性质被广泛地应用于图论和离散数学的教学和研究中。对于复杂性问题的研究，完全图也是一个常见的研究对象。虽然完全图不是平面图，但其特殊性质及在研究中的重要性是值得探讨的。