平面图 首先，我们来理解平面图的直观定义。一个图被称为 平面图 ，如果它可以被画在一个平面上，并且其任意两条边都只在顶点处相交。这种画法被称为图的一个 平面嵌入 。 例如，一个包含5个顶点的完全图（K5）和一个包含3组，每组3个顶点的完全二分图（K3,3）在直观上似乎很难在不交叉的情况下画出。这引出了平面图理论的一个核心定理。 接下来是平面图的一个关键性质，即 欧拉公式 。对于一个连通的平面图（其平面嵌入将平面划分成若干个区域，称为 面 ），设其顶点数为V，边数为E，面数为F（包括最外部的无限面），则欧拉公式表述为： V - E + F = 2 这个公式揭示了平面图中顶点、边和面数量之间的深刻联系，是证明许多平面图性质的基础工具。 利用欧拉公式，我们可以推导出平面图的一些必要条件。对于一个顶点数V ≥ 3的连通简单平面图，其边数E满足不等式：E ≤ 3V - 6。这个不等式可以用来证明某些图不是平面图。例如，K5有V=5，E=10，但3* 5-6=9，10>9，所以K5不是平面图。 那么，如何系统地判断一个图是否为平面图呢？这引出了 库拉托夫斯基定理 。该定理指出，一个图是平面图，当且仅当它不包含任何同胚于K5或K3,3的子图。这里的“同胚”是指可以通过在图的边上插入或删除度数为2的顶点而相互转化。这个定理给出了平面图一个纯粹的组合数学定义，不依赖于画法。 平面图理论还有一个对偶的应用，即 对偶图 。给定一个平面图G的平面嵌入，我们可以构造其对偶图G* ：在G的每个面内放置G 的一个顶点；对于G的每一条边e，如果它分隔了面f1和f2，则在G 中连接f1和f2对应的顶点，这条边记为e* 。对偶图本身也是一个平面图，并且(G* )* 与 G 是同构的。对偶图的概念在图着色、网络流等领域有重要应用。