Planar Graphs: Determination and Euler’s Formula Applications | 平面图的判定与欧拉公式应用

📚 Planar Graphs: Determination and Euler’s Formula Applications | 平面图的判定与欧拉公式应用

In the IB Mathematics Analysis and Approaches (AA) and Applications and Interpretation (AI) syllabi, graph theory appears in the discrete mathematics option, where planar graphs form a fascinating and examinable topic. This article explores how to determine whether a graph is planar, and how Euler’s formula can be applied to solve problems — from simple edge-counting exercises to rigorous non-planarity proofs.

在 IB 数学分析与方法（AA）及应用与解释（AI）课程中，图论出现在离散数学选修部分，而平面图是其中极具魅力且常考的内容。本文将深入探讨如何判定一个图是否为平面图，以及如何运用欧拉公式解决问题——从简单的边数计算到严格的非平面性证明。

1. What Is a Planar Graph? | 什么是平面图？

Before applying Euler’s formula, we must establish a clear definition. A graph is said to be planar if it can be drawn in a plane without any of its edges crossing. Crucially, a graph may appear non-planar in one drawing, yet a different drawing may eliminate all crossings — we only require the existence of at least one crossing-free drawing.

在应用欧拉公式之前，我们必须确立一个清晰的定义。如果一个图可以画在平面上且没有任何一条边相交，则该图称为平面图。关键之处在于，一个图在某种画法中可能看起来是非平面的，但换一种画法可能消除所有交叉——我们仅要求存在至少一种无交叉的画法。

A graph G is planar ⇔ ∃ a drawing of G on the plane with no edge crossings.

图 G 是平面图 ⇔ 存在 G 的一种平面画法，使得没有任何边相交。

For example, the complete graph K₄ is normally drawn as a quadrilateral with both diagonals crossing, but by moving one vertex inside the quadrilateral, we can draw K₄ with no crossings. Thus K₄ is planar.

例如，完全图 K₄ 通常画成四边形并带两条相交的对角线，但若将一个顶点移动到四边形内部，我们就可以无交叉地画出 K₄。因此 K₄ 是平面图。

---

2. Euler’s Formula | 欧拉公式

Euler’s formula is the cornerstone of planar graph theory. For a connected planar graph drawn in the plane, let V denote the number of vertices, E the number of edges, and F the number of faces (including the unbounded outer face). Then:

欧拉公式是平面图理论的基石。对于一个画在平面上的连通平面图，设 V 为顶点数，E 为边数，F 为面数（包括无界的外部面），则有：

V − E + F = 2

This elegant identity holds for every connected planar graph, regardless of how it is drawn, provided no edges cross. The outer face counts as one face — a point students frequently forget in examinations.

这一优美的恒等式对所有连通平面图都成立，无论其画法如何，只要没有边相交。外部面算作一个面——这是学生在考试中经常忘记的一个要点。

If the graph is disconnected with c connected components, the formula generalises to V − E + F = 1 + c. In most IB questions, however, the connected case suffices.

如果图不连通且有 c 个连通分量，公式推广为 V − E + F = 1 + c。不过在大多数 IB 题目中，连通的情况已经足够。

---

3. Degrees and Face Degrees | 顶点度与面度

To apply Euler’s formula effectively, we need to relate edges to degrees. Recall that the sum of the degrees of all vertices equals twice the number of edges: Σdeg(v) = 2E. This is the Handshaking Lemma, valid for any graph.

为了有效应用欧拉公式，我们需要将边与度联系起来。回顾所有顶点度数之和等于边数的两倍：Σdeg(v) = 2E。这就是握手引理，对所有图均成立。

Similarly, for a planar graph, we can define the degree of a face as the number of edges in its boundary walk. A remarkable duality exists: summing the degrees of all faces also equals 2E, because each edge borders exactly two faces (or is counted twice if it borders the same face on both sides). Thus:

类似地，对于平面图，我们可以定义面的度为该面边界游走中的边数。这里存在一个显著的二元性：所有面的度数之和也等于 2E，因为每条边恰好邻接两个面（如果边的两侧属于同一个面，则被计算两次）。因此：

Σdeg(f) = 2E

This double-counting technique is fundamental in many planarity proofs and IB examination problems.

这种双重计数的技巧在许多平面性证明和 IB 考试题目中都是基础性的工具。

---

4. Proving K₅ and K₃,₃ Are Non-Planar | 证明 K₅ 与 K₃,₃ 是非平面图

Two graphs are of paramount importance in planarity theory. The complete graph K₅ (five vertices, all mutually connected) and the complete bipartite graph K₃,₃ (two sets of three vertices, every vertex in one set joined to every vertex in the other). Both are non-planar, and Euler’s formula gives us a rigorous proof.

在平面图理论中，有两个图具有至高无上的重要性。完全图 K₅（五个顶点，两两相连）和完全二分图 K₃,₃（两个顶点集各含三个顶点，一个集中的每个顶点与另一个集中的每个顶点相连）。两者均为非平面图，欧拉公式为我们提供了严格的证明。

Case 1: K₅. Here V = 5, E = 10. Suppose K₅ were planar and connected. By Euler’s formula, F = E − V + 2 = 10 − 5 + 2 = 7 faces. In a simple planar graph, every face has degree at least 3 (a face of degree 1 or 2 would require a loop or multiple edge). Hence Σdeg(f) ≥ 3F = 21. But Σdeg(f) = 2E = 20, a contradiction. Therefore K₅ is non-planar.

情形 1：K₅。这里 V = 5，E = 10。假设 K₅ 是连通的平面图。由欧拉公式，F = E − V + 2 = 10 − 5 + 2 = 7 个面。在简单平面图中，每个面的度至少为 3（度为 1 或 2 的面需要环或重边）。因此 Σdeg(f) ≥ 3F = 21。但 Σdeg(f) = 2E = 20，矛盾。故 K₅ 是非平面图。

Case 2: K₃,₃. Here V = 6, E = 9. K₃,₃ is bipartite, so it contains no odd cycles; every face must have degree at least 4. If planar, Euler’s formula gives F = E − V + 2 = 9 − 6 + 2 = 5. Then Σdeg(f) ≥ 4F = 20, but Σdeg(f) = 2E = 18, a contradiction. Hence K₃,₃ is non-planar.

情形 2：K₃,₃。这里 V = 6，E = 9。K₃,₃ 是二分图，因此不含奇数环；每个面的度至少为 4。若为平面图，欧拉公式给出 F = E − V + 2 = 9 − 6 + 2 = 5。则 Σdeg(f) ≥ 4F = 20，但 Σdeg(f) = 2E = 18，矛盾。因此 K₃,₃ 是非平面图。

These two contradictions illustrate the power of combining Euler’s formula with face-degree bounds.

这两个矛盾论证展示了将欧拉公式与面度下界结合使用的强大威力。

---

5. Corollaries: Edge Bounds | 推论：边数上界

From the face-degree argument, we can derive two frequently used inequalities. For a connected simple planar graph with V ≥ 3:

由面度论证，我们可以推导出两个常用不等式。对于 V ≥ 3 的连通简单平面图：

E ≤ 3V − 6

This follows because each face has degree at least 3, so 2E = Σdeg(f) ≥ 3F = 3(2 − V + E), which rearranges to E ≤ 3V − 6.

这是因为每个面的度至少为 3，所以 2E = Σdeg(f) ≥ 3F = 3(2 − V + E)，整理即得 E ≤ 3V − 6。

For bipartite planar graphs, every face has degree at least 4, yielding the stronger bound:

对于二分平面图，每个面的度至少为 4，因此得到更强的上界：

E ≤ 2V − 4

These inequalities provide quick tests: if E > 3V − 6, the graph is definitely non-planar. For example, K₅ has E = 10 > 3×5 − 6 = 9, so non-planar immediately. However, note that the bound is necessary but not sufficient — passing the test does not guarantee planarity.

这些不等式提供了快速检验：若 E > 3V − 6，则图必定是非平面的。例如，K₅ 的 E = 10 > 3×5 − 6 = 9，因此立即判定为非平面图。但需注意，该条件是必要而非充分条件——通过检验并不能保证图是平面的。

---

6. Kuratowski’s Theorem | 库拉托夫斯基定理

The definitive characterisation of planar graphs comes from Kuratowski, who proved in 1930 that a graph is planar if and only if it contains no subgraph homeomorphic to K₅ or K₃,₃. Two graphs are homeomorphic if one can be obtained from the other by subdividing edges (inserting vertices of degree 2 along edges).

平面图的终极判定标准来自库拉托夫斯基，他在 1930 年证明：一个图是平面图当且仅当它不包含任何与 K₅ 或 K₃,₃ 同胚的子图。两个图同胚，是指其中之一可以通过细分边（在边上插入度为 2 的顶点）而得到另一个。

An equivalent formulation uses minors: a graph is planar if and only if it contains neither K₅ nor K₃,₃ as a minor. A minor is obtained by deleting vertices, deleting edges, and contracting edges.

等价的表述使用子式：一个图是平面图当且仅当它既不以 K₅ 也不以 K₃,₃ 作为子式。子式通过删除顶点、删除边和收缩边得到。

Formulation | 表述	Statement | 命题内容
Homeomorphism | 同胚	G is planar ⇔ G has no subgraph homeomorphic to K₅ or K₃,₃ | G 是平面图 ⇔ G 不含与 K₅ 或 K₃,₃ 同胚的子图
Minor | 子式	G is planar ⇔ G has neither K₅ nor K₃,₃ as a minor | G 是平面图 ⇔ G 不以 K₅ 或 K₃,₃ 为子式

In IB examinations, Kuratowski’s theorem is often tested indirectly: students may be asked to show that a given graph is non-planar by identifying a homeomorphic copy of K₃,₃ inside it.

在 IB 考试中，库拉托夫斯基定理经常以间接方式考查：学生可能被要求在给定的图中识别出与 K₃,₃ 同胚的子图，从而证明该图是非平面的。

---

7. Worked Example: A Pentagon with All Diagonals | 例题：五边形及其所有对角线

Consider the graph formed by a regular pentagon plus all five diagonals. This is actually K₅, so we already know it is non-planar. But let us verify the edge bound: V = 5, E = 10, and 3V − 6 = 9. Since 10 > 9, the graph is non-planar by the corollary.

考虑一个正五边形加上全部五条对角线所构成的图。这实际上就是 K₅，因此我们已知它是非平面的。但让我们用边数上界来验证：V = 5，E = 10，而 3V − 6 = 9。因为 10 > 9，根据推论该图是非平面图。

This example demonstrates how quickly the edge bound disposes of a case that would otherwise require extensive drawing attempts.

这个例子展示了边数上界如何快速解决一个否则需要大量画图尝试的问题。

---

8. Worked Example: The Utility Problem | 例题：公用事业问题

The classic “three utilities” problem asks: can three houses be connected to three utility plants (water, gas, electricity) without any pipes crossing? This is precisely K₃,₃. Using V = 6, E = 9, the bipartite bound gives 2V − 4 = 8, and since 9 > 8, K₃,₃ is non-planar. The answer is no.

经典的”三家公用事业”问题问：三栋房子能否连接到三个公用事业设施（水、气、电）而没有任何管线交叉？这正是 K₃,₃。利用 V = 6，E = 9，二分图边界给出 2V − 4 = 8，因为 9 > 8，所以 K₃,₃ 是非平面图。答案是不可以。

This historical problem, popularised as a puzzle in the early 20th century, was among the motivations for the development of planar graph theory.

这个历史性问题在 20 世纪初作为谜题而广为人知，是推动平面图理论发展的重要动力之一。

---

9. Platonic Solids and Euler’s Formula | 柏拉图立体与欧拉公式

Euler’s formula has a beautiful application in three-dimensional geometry. Each Platonic solid — tetrahedron, cube, octahedron, dodecahedron, icosahedron — can be projected onto a plane, giving a connected planar graph. The formula V − E + F = 2 holds for all of them.

欧拉公式在三维几何中有一个美妙的应用。每个柏拉图立体——正四面体、正方体、正八面体、正十二面体、正二十面体——都可以投影到平面上，得到连通平面图。公式 V − E + F = 2 对它们全部成立。

Indeed, the formula is historically significant: it was Euler’s observation about polyhedra in 1758 that laid the foundation for modern graph theory. The relationship between the faces of a polyhedron and the faces (regions) of a planar drawing is direct — projecting the polyhedron’s skeleton onto a plane maps its faces to the regions of the drawing, including the outer face.

事实上，该公式具有重要的历史意义：正是欧拉在 1758 年对多面体的观察奠定了现代图论的基础。多面体的面与平面画法中的面（区域）之间的关系是直接的——将多面体的骨架投影到平面上，将其面映射为画法中的区域，包括外部面。

For IB students studying both geometry and graph theory, this bridge between disciplines is a powerful reminder of the unity of mathematics.

对于同时学习几何与图论的 IB 学生来说，这一跨学科的桥梁有力地提醒我们数学的统一性。

---

10. Face Counting in IB-Style Problems | IB 风格题目中的面数计算

A common IB examination question provides a planar graph with specific vertex degrees and asks for the number of faces. For example: a connected planar graph has 12 vertices, each of degree 3. Find the number of faces.

一个常见的 IB 考试题目给出具有特定顶点度的平面图，要求计算面数。例如：一个连通平面图有 12 个顶点，每个顶点的度均为 3。求面数。

Solution. By the Handshaking Lemma, 2E = Σdeg(v) = 12 × 3 = 36, so E = 18. By Euler’s formula, F = E − V + 2 = 18 − 12 + 2 = 8. The graph has 8 faces.

解答。由握手引理，2E = Σdeg(v) = 12 × 3 = 36，故 E = 18。由欧拉公式，F = E − V + 2 = 18 − 12 + 2 = 8。该图有 8 个面。

Such problems test whether students can connect the Handshaking Lemma with Euler’s formula — a standard two-step technique. Another variation provides the edge/face counts and asks for a property of vertex degrees.

此类问题考查学生能否将握手引理与欧拉公式相连接——这是标准的两步技巧。另一种变体给出边数与面数，要求推断顶点度的性质。

---

11. Dual Graphs | 对偶图

Every connected planar graph has a dual graph: place a vertex in each face of the original graph, and for each edge e, draw an edge crossing e to connect the two vertices in the faces adjacent to e. The dual of a planar graph is always planar, and the dual of the dual returns to the original graph (for connected graphs).

每个连通平面图都有一个对偶图：在原始图的每个面中放置一个顶点，对于每条边 e，画一条穿过 e 的边连接 e 两侧面中的两个顶点。平面图的对偶图总是平面的，而对偶的对偶（对连通图）回到原始图。

The relationship is elegant: if G has V vertices, E edges, and F faces, then its dual G* has F vertices, E edges, and V faces. The edge count is preserved, which is a quick check when constructing duals.

这种关系非常优美：如果 G 有 V 个顶点、E 条边和 F 个面，那么其对偶图 G* 有 F 个顶点、E 条边和 V 个面。边数保持不变，这在构造对偶图时是一个快速检验手段。

Dual graphs appear occasionally in IB Paper 3 questions, often in the context of map colouring or network design.

对偶图偶尔出现在 IB Paper 3 的题目中，通常在地图着色或网络设计的背景下出现。

---

12. Exam Tips and Common Pitfalls | 考试技巧与常见误区

To succeed in planarity questions on the IB examination, keep the following strategies in mind:

要在 IB 考试中成功解答平面图问题，请牢记以下策略：

• Always count the outer face. | 始终将外部面计入面数。

  The most frequent mistake is recording F = 2 instead of F = 3 for a triangle drawn with one face inside and the outer face. | 最常见的错误是将一个三角形记为 F = 2 而不是 F = 3——三角形有一个内部面和一个外部面。

• Check whether the graph is simple. | 检查图是否为简单图。

  The inequalities E ≤ 3V − 6 and E ≤ 2V − 4 apply only to simple graphs with V ≥ 3 and V ≥ 4 respectively. | 不等式 E ≤ 3V − 6 和 E ≤ 2V − 4 仅分别适用于 V ≥ 3 和 V ≥ 4 的简单图。

• Verify connectivity. | 确认连通性。

  Euler’s formula requires a connected graph; applying it to a disconnected graph without the correction term V − E + F = 1 + c leads to wrong results. | 欧拉公式要求图是连通的；若对非连通图不加修正项 V − E + F = 1 + c 而直接使用，将得到错误结果。

• Know when to use which bound. | 知道何时使用哪个界限。

  For bipartite graphs, always use the stronger bound E ≤ 2V − 4. | 对于二分图，始终使用更强的界限 E ≤ 2V − 4。

• Practice redrawing. | 练习重画图。

  In planarity determination, try moving vertices and rerouting edges before concluding non-planarity. | 在判定平面性时，先尝试移动顶点和重新规划边，再下非平面的结论。

• Use the face-degree sum identity confidently. | 自信地使用面度求和恒等式。

  The double-counting technique Σdeg(f) = 2E is the engine behind nearly every planarity proof in the IB syllabus. | 双重计数技巧 Σdeg(f) = 2E 是 IB 大纲中几乎所有平面性证明背后的引擎。

With these techniques, planar graph questions become routine rather than intimidating. Master the definitions, memorise the key bounds, and practise rewriting graphs.

掌握了这些技巧，平面图题目将变得常规而非令人生畏。记住定义，牢记关键界限，并多加练习重画图。

---

Published by TutorHao | Mathematics Revision Series | aleveler.com

更多咨询请联系16621398022（同微信）