📚 Planar Graphs | 平面图
In graph theory, a planar graph is a graph that can be drawn on a flat surface without any edges crossing except at their endpoints. This concept plays a central role in topological graph theory, circuit board design, and geographical map representation. In this IB Mathematics revision article, we will examine the definition, faces, Euler’s formula, planarity criteria, and the famous Kuratowski’s theorem, as well as practical methods for checking whether a given graph is planar.
在图论中，平面图是指能够画在平面上且除了在端点处以外边与边互不交叉的图。这一概念在拓扑图论、电路板设计以及地图表示中都占据核心地位。在这篇 IB 数学复习文章中，我们将探讨平面图的定义、面、欧拉公式、平面性判定条件以及著名的库拉托夫斯基定理，并介绍判断给定图是否为平面图的实用方法。
1. What is a Planar Graph? | 什么是平面图？
A graph G is called planar if there exists a drawing of G in the plane in which no two edges cross each other. It is essential to distinguish between a planar graph (which can be drawn without crossing) and a plane graph (a specific crossing-free drawing already given in the plane). For example, any tree is planar, and the complete graph K4 is planar, although its standard drawing with straight lines often contains a crossing – a planar embedding of K4 can remove that crossing by curving one edge.
如果存在图 G 在平面上的一种画法，使得任意两条边均不相交，则称 G 为平面图。必须区分“平面图”（可以无交叉画出）与“平面嵌入图”（已在平面上给出的一种具体无交叉画法）。例如，任何树都是平面图，完全图 K4 也是平面图，尽管其标准直线画法通常会有交叉，但通过将一条边画成曲线就可以消除该交叉。
2. Planar Embeddings and Faces | 平面嵌入与面
A plane graph divides the plane into connected regions called faces. One of these regions is unbounded and is called the outer face or infinite face. Each face is bounded by a closed walk along edges, and the degree of a face is the number of edges encountered when walking around its boundary (with cut-edges counted twice). The number of faces, denoted by f, depends on the specific embedding, but the relationship with vertices and edges remains invariant for connected planar graphs.
一个平面嵌入图将平面分割成若干连通区域，这些区域称为面。其中有一个面是无界的，称为外部面或无限面。每个面都由沿着边的一条闭途径围成，面的度数是指沿其边界行走时经过的边数（割边需计算两次）。面数通常用 f 表示，其具体数值依赖于嵌入方式，但对于连通平面图，顶点、边和面之间的关系保持不变。
3. Euler’s Formula | 欧拉公式
One of the most important results for planar graphs is Euler’s formula. For any connected plane graph with v vertices, e edges, and f faces (including the outer face), the following identity holds:
平面图最重要的结论之一是欧拉公式。对于任意一个具有 v 个顶点、e 条边和 f 个面（包括外部面）的连通平面嵌入图，下述恒等式成立：
v − e + f = 2
This remarkable formula serves as a bridge between combinatorial data (vertices and edges) and topological information (faces). It remains true for any planar embedding of the same connected planar graph, because the planar graph will always have some embedding satisfying the formula.
这一优美的公式在组合数据（顶点与边）和拓扑信息（面）之间架起了一座桥梁。对于同一个连通平面图的任何平面嵌入，该公式均成立，因为平面图总存在某种满足该公式的嵌入。
4. Proof Sketch of Euler’s Formula | 欧拉公式的证明概要
A proof can be given by induction on the number of edges e. Start with a spanning tree of the plane graph, which has v vertices, v−1 edges, and only one face (the outer face). For a tree, v − (v−1) + 1 = 2. Then add the remaining edges one by one; each added edge splits an existing face into two, increasing both e and f by 1, thereby preserving the value v − e + f. Hence the formula holds for the whole graph.
可以通过对边数 e 进行归纳来证明。从图的一棵生成树开始，其具有 v 个顶点、v−1 条边，且仅有一个面（外部面）。对于树，v − (v−1) + 1 = 2。然后逐一添加剩余的边；每添加一条边都会将某个现有的面一分为二，使得 e 和 f 同时增加 1，从而保持 v − e + f 的值不变。因此整个图依然满足该公式。
5. Consequences: Upper Bounds on Edges | 推论：边数的上界
For a simple connected planar graph with v ≥ 3 vertices, each face is bounded by at least 3 edges, so 3f ≤ 2e (since each edge contributes to at most two faces). Substituting f from Euler’s formula gives f = e − v + 2, leading to 3(e − v + 2) ≤ 2e, which simplifies to:
对于具有 v ≥ 3 个顶点的简单连通平面图，每个面至少由 3 条边围成，故有 3f ≤ 2e（因为每条边至多为两个面所共用）。利用欧拉公式将 f = e − v + 2 代入，得到 3(e − v + 2) ≤ 2e，整理后可得：
e ≤ 3v − 6
If the graph contains no triangles (i.e., it is triangle-free), the minimum face degree is 4, giving 4f ≤ 2e and consequently e ≤ 2v − 4. These inequalities provide powerful necessary conditions for planarity and can quickly prove that certain dense graphs are non-planar.
如果图中不含三角形（即无 3-圈），则面的最小度数为 4，此时有 4f ≤ 2e，进而得到 e ≤ 2v − 4。这些不等式为平面性提供了强有力的必要条件，能够快速证明某些稠密图是非平面图。
6. Non-planar Graphs: K₅ and K₃,₃ | 非平面图：K₅ 与 K₃,₃
The complete graph on five vertices, K5, has v = 5 and e = 10. Substituting into the inequality e ≤ 3v − 6 gives 10 ≤ 9, a contradiction. Hence K5 cannot be planar. The complete bipartite graph K3,3 has v = 6 and e = 9. Because it is bipartite, it contains no triangles, so we use e ≤ 2v − 4, yielding 9 ≤ 8, which is false. Therefore K3,3 is also non-planar. These two graphs are the fundamental building blocks for understanding non-planarity.
五个顶点的完全图 K5 有 v = 5，e = 10。代入不等式 e ≤ 3v − 6 得到 10 ≤ 9，矛盾，故 K5 不可能是平面图。完全二部图 K3,3 有 v = 6，e = 9。由于它是二部图，不含三角形，因此应使用 e ≤ 2v − 4，得到 9 ≤ 8，不成立。所以 K3,3 也是非平面图。这两个图是理解非平面性的基本构件。
7. Kuratowski’s Theorem | 库拉托夫斯基定理
Kuratowski’s theorem provides a complete characterization of planar graphs: a finite graph is planar if and only if it does not contain a subgraph that is a subdivision of K5 or K3,3. A subdivision of a graph is obtained by inserting vertices of degree 2 along its edges (effectively replacing edges by paths). This theorem means that K5 and K3,3 are the sole obstructions to planarity for all finite graphs.
库拉托夫斯基定理给出了平面图的完整刻画：一个有限图是平面图当且仅当它不包含 K5 或 K3,3 的细分作为子图。图的细分是通过在边上插入度数为 2 的顶点（即将边替换为路径）得到的。该定理表明，K5 和 K3,3 是所有有限图平面性的唯一障碍。
8. Planarity Testing in Practice | 平面性检测实践
To show that a graph is planar, it suffices to produce a planar embedding. To show it is non-planar, one can either use the edge-bound inequalities (if they are violated) or search for a K5 or K3,3 subdivision. Common techniques include identifying a subgraph homeomorphic to K5 or K3,3, or using edge contraction to reduce to one of these graphs. In examinations, you are often asked to prove non-planarity by finding a subdivision or by applying the inequalities after verifying that the graph is sufficiently dense.
要证明一个图是平面图，只需画出一个无交叉的平面嵌入即可。要证明其非平面，可以利用边数不等式（若不等式不成立）或寻找 K5 或 K3,3 的细分。常用技巧包括识别出一个与 K5 或 K3,3 同胚的子图，或者通过边收缩将其化为这些图之一。在考试中，常要求通过找出细分或验证图的稠密度适合不等式来证明非平面性。
9. Coloring Planar Graphs | 平面图着色简介
Planar graphs are famously linked to the Four Colour Theorem, which states that the vertices of any planar graph can be coloured with at most four colours so that adjacent vertices have different colours. While the proof is complex, the theorem highlights a deep topological property. For face colouring of plane graphs, the dual graph concept transforms the problem into vertex colouring. In practice, many planar graphs are 3-colourable or even 2-colourable, and exam problems often involve showing that a specific planar graph requires exactly χ(G) colours.
平面图与四色定理有着著名的联系，该定理指出任何平面图的顶点都可以用至多四种颜色进行着色，使得相邻顶点颜色不同。虽然证明十分复杂，但该定理揭示了一个深刻的拓扑性质。对于平面嵌入图的面着色问题，可通过构造对偶图将其转化为顶点着色问题。在实际中，许多平面图是三色甚至二色可着色的，考试题目常要求证明某个平面图恰好需要 χ(G) 种颜色。
10. Key Takeaways and Exam Tips | 核心要点与考试提示
Remember Euler’s formula v − e + f = 2 and the derived bounds e ≤ 3v − 6 (general) and e ≤ 2v − 4 (triangle-free). Recognise K5 and K3,3 instantaneously and know that any subdivision of them renders a graph non-planar. When tackling an IB question, always check if a quick inequality test suffices; otherwise, attempt to locate a subdivision. Drawing clear diagrams and carefully tracing paths with inserted degree-2 vertices can help identify hidden K3,3 or K5 subdivisions.
牢记欧拉公式 v − e + f = 2 及其导出的界 e ≤ 3v − 6（一般情况）和 e ≤ 2v − 4（无三角形情况）。快速识别 K5 和 K3,3，并知道它们的任何细分都会导致图非平面。在解答 IB 问题时，应先检查简单的不等式检验是否足够；否则尝试寻找细分。绘制清晰的图示并仔细追踪带有度数为 2 的插入顶点的路径，有助于发现隐藏的 K3,3 或 K5 细分。
Published by TutorHao | Mathematics Revision Series | aleveler.com
更多咨询请联系16621398022（同微信）
屏轩国际教育cambridge primary/secondary checkpoint, cat4, ukiset,ukcat,igcse,alevel,PAT,STEP,MAT, ibdp,ap,ssat,sat,sat2课程辅导，国外大学本科硕士研究生博士课程论文辅导Cancel reply