平面图与欧拉公式

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. 什么样的图是平面图

一个图称为平面图，是指它可以画在一张平坦的纸上，使任意两条边都不交叉。每个顶点画成一个点，每条边画成连接其两个端点的一条曲线，并且曲线只允许在它们共享的顶点处相遇。遵守这些规则的画法称为图的一个平面画法或一个嵌入，而一个图连同一个固定的嵌入称为一个平图。

这两个词的区别比乍看之下更重要。平面图（planar）这个词说的是图的性质：它问的是是否存在某种无交叉的画法。平图（plane）这个词描述的则是一个特定的画法。一个图可以有一种完全合格的平面画法，同时还有上百种布满交叉的画法，而那些糟糕的画法都不会对它产生不利影响。完全图 K4 是标准的第一个例子。画成带两条对角线的正方形时，两条对角线相交。把一个顶点移到另外三个顶点构成的三角形中间，所有交叉就都消失了，所以 K4 是平面图。

这幅图还引入了贯穿全文的例子，即三棱柱。它有一个外三角形 A, B, C、一个内三角形 D, E, F，以及三条辐条，分别把 A 连到 D， B 连到 E，以及把 C 连到 F：

V = {A, B, C, D, E, F}                                   6 个顶点
E = {AB, BC, CA, DE, EF, FD, AD, BE, CF}                  9 条边

有三点实际说明，可以确定这个定义依赖什么、不依赖什么。第一，自环和平行边永远不影响平面性：一条边的第二个副本可以画成紧贴第一条边的一条细曲线，自环则可以画成顶点旁的一个小卷曲。一个多重图是平面图，当且仅当它的底层简单图是平面图，这也是本文后面的计数上界都针对简单图来陈述的原因。第二，平面与球面可以互换。球极投影可以把球面上的画法变成平面上的画法，反之亦然，所以一个图是平面图，当且仅当它能无交叉地画在一个球的表面上。第三，从来不需要曲线。Wagner 在 1936 年、Fáry 在 1948 年各自独立证明了：每个简单平面图都有一种平面画法，其中每条边都是直线段，这一结果通常称为 Fáry 定理。

2. 面：画法划分出的区域

沿着边把一个平面画法从纸上剪下来，纸就会分成若干块。这些块就是该画法的面。其中恰好有一个是无界的，它称为外部面，忘记把它算进去是整个主题中最常见的疏忽。三棱柱有五个面：内三角形 D, E, F，三个四边形面 A, B, E, D、 B, C, F, E 和 C, A, D, F，以及外部面，它位于三角形 A, B, C之外。

一个面的长度（或度）是沿其边界走一圈时经过的边数，并有一条让计数保持精确的规则：如果一条边两侧是同一个面，例如树的边，就要走两次、计两次。有了这条规则，每条边对总数恰好贡献 2，每一侧各贡献 1，于是面也服从它们自己的握手引理：

各面长度之和 = 2e

三棱柱：  3 + 4 + 4 + 4 + 3  =  18  =  2 × 9
         （内三角形、三个四边形、以 A, B, C 为边界的外部面）

这个等式就是顶点与边指南中的顶点握手引理，只不过把顶点换成了面，它支撑着第 4 节和第 5 节中的所有上界。面属于画法而不属于图，所以一个有多种平面画法的图，在不同画法中可以有不同长度的面。用长度分别为 1、2、3、4 的四条路径连接两个顶点 x 和 y。按这个顺序绕 x 排列时，相邻的路径围成长度为 3、5、7、5 的面。交换中间两条路径，面的长度就变成 4、5、6、5。不变的是面的个数，两种画法中都是四个，下一节将证明这并非偶然。

3. 欧拉公式

数一数任何连通平面画法的顶点、边和面，这三者的某个组合永远不变。

欧拉公式。对每个有 v 个顶点、 e 条边和 f 个面的连通平图，都有 v − e + f = 2。

对于三棱柱， 6 − 9 + 5 = 2。对于无交叉地画出的 K4， 4 − 6 + 4 = 2。对于单个顶点， 1 − 0 + 1 = 2，因为它周围的空平面就是一个面。这个证明足够短，可以完整给出；它值得一读，因为同样的思想，即删除一条边并观察什么发生了变化，贯穿了这个主题的其余部分。

证明。固定顶点数，对边数进行归纳。边数尽可能少的连通图是树，而树满足 e = v − 1 （这是图论中的树一文所收集的等价刻画之一）。树不含圈，所以它的画法不围出任何区域，只有一个面。于是 v − (v − 1) + 1 = 2，得证。

如果这个连通图不是树，它就含有一个圈。在这个圈上选一条边并删除它。图仍然连通，因为圈的其余部分仍然连接着被删边的两个端点。在画法中，这个圈是一条闭曲线，根据 Jordan 曲线定理，它把平面分成内部和外部。因此被删除的边两侧是不同的面，一个在圈内，一个在圈外，删除它就把这两个面合并为一个。所以 e 减少一， f 也减少一，而 v − e + f 保持不变。由归纳假设，较小的图满足这个公式，所以原来的图也满足。

这个公式有一个容易被忽略的推论。面的个数 f = e − v + 2只取决于图，而与它的画法无关。这就是第 2 节中四路径图的两种画法都有四个面的原因：由于 v = 8 且 e = 10，该图的每种平面画法都有 10 − 8 + 2 = 4 个面。如果图不连通，所有部分共享外部面，公式就变成 v − e + f = 1 + k，适用于有 k 个连通分量的图。

这个公式很容易用机器检验。下面的函数接受一个以坐标给出的无交叉直线画法，沿着边行走来追踪每个面，并且在每个顶点处总是按顺时针顺序转向下一条边。每条边有两侧，每一侧恰好被走一次。

from math import atan2

def faces(pos, edges):
    """追踪连通图的无交叉直线画法中的所有面。"""
    nbrs = {v: [] for v in pos}
    for u, v in edges:
        nbrs[u].append(v)
        nbrs[v].append(u)
    for v, ws in nbrs.items():               # 邻居按逆时针顺序排列
        x, y = pos[v]
        ws.sort(key=lambda w: atan2(pos[w][1] - y, pos[w][0] - x))
    seen, found = set(), []
    for u, v in edges:
        for dart in ((u, v), (v, u)):        # 每条边有两侧
            face = []
            while dart not in seen:
                seen.add(dart)
                a, b = dart
                face.append(a)
                ws = nbrs[b]
                dart = (b, ws[ws.index(a) - 1])  # 在 b 处，按顺时针转向下一条边
            if face:
                found.append(face)
    return found

pos = {'A': (0, 4), 'B': (-3.5, -2), 'C': (3.5, -2),
       'D': (0, 1.6), 'E': (-1.4, -0.8), 'F': (1.4, -0.8)}
edges = [('A', 'B'), ('B', 'C'), ('C', 'A'), ('D', 'E'), ('E', 'F'),
         ('F', 'D'), ('A', 'D'), ('B', 'E'), ('C', 'F')]
fs = faces(pos, edges)
v, e, f = len(pos), len(edges), len(fs)
print(v, e, f, v - e + f)
# 6 9 5 2
print(sorted(len(face) for face in fs))
# [3, 3, 4, 4, 4]

这五个面的长度正是第 2 节中数出的那些，它们的和为 18 = 2e。同样的追踪过程，如果在抽象的邻居顺序列表而不是坐标上运行，正是平面性程序库存储嵌入的方式：一个图的嵌入完全由每个顶点周围边的循环顺序确定，这种描述称为旋转系统。

多面体，以及这个公式的由来

Euler 最初陈述这个公式时，针对的不是图，而是多面体，即由平坦的面围成的立体。他在 1750 年 11 月写给 Christian Goldbach 的一封信中陈述了它，并在圣彼得堡科学院期刊上的两篇论文中发表，所在的那一卷标注为 1752 和 1753 年，实际于 1758 年印出。透过凸多面体的一个面去看，就能把它画到平面上，这个面随之成为外部面，而它的角、棱和面就成为一个平图的顶点、边和面。五种正多面体给出的答案都相同：

这段历史有两个著名的转折。René Descartes 曾在一份如今已经失传的手稿中写下一个等价的关系式，以角的形式表述；Leibniz 于 1675 或 1676 年在巴黎制作的一份抄本在十九世纪被重新发现，并于 1859–60 年发表。而 Euler 自己的论证，即从立体上一次切掉一个角，按现代标准并不是完整的证明。Adrien-Marie Legendre 于 1794 年给出了第一个完整证明，用的是画在球面上的多边形的面积；Augustin-Louis Cauchy 于 1813 年发表了另一个证明，把多面体压平成平面上的一个网络并逐块拆解，思路与上面的论证相近。Imre Lakatos 的著作《证明与反驳》（1976）就围绕那些打破这个公式的奇怪“多面体”展开，例如表面有一个洞的画框。图论的历史一文把这个结果放在 Euler 的另一项奠基性贡献，即柯尼斯堡七桥问题旁边。

4. 平面图最多能有多少条边？

欧拉公式与面的握手引理结合后，就变成了对边数的硬性限制。这个论证是平面图理论中最有用的三行。

定理。一个有 v ≥ 3 个顶点的简单平面图至多有 3v − 6 条边。如果它还不含三角形，则至多有 2v − 4 条边。

证明。取一个平面画法，并先假设图是连通的。在至少有三个顶点的简单图中，每个面的长度至少为 3：长度为 1 的面需要一个自环，长度为 2 的面需要两条平行边，除非整个图只是一条边，而 v ≥ 3 排除了这种情况。对所有面求和，得 3f ≤ 2e。欧拉公式给出 f = 2 − v + e，所以 3(2 − v + e) ≤ 2e，整理后即 e ≤ 3v − 6。如果图不含三角形，每个面的长度至少为 4，所以 4f ≤ 2e，同样的代入给出 e ≤ 2v − 4。对于不连通的平面图，可以在其连通分量之间添加边而不产生任何交叉，而添加边只会让不等式更难满足，所以上界对它同样成立。

第二个上界涵盖每个二分图，因为二分图没有奇环，特别是没有三角形。两个上界都是同一个不等式的特例。如果一个连通平面图中最短圈的长度，也就是它的围长，等于 g，那么每个面的长度都至少为 g，同样的三行推导给出

e ≤ g(v − 2) / (g − 2)

g = 3   →   e ≤ 3v − 6        （任意简单平面图，v ≥ 3）
g = 4   →   e ≤ 2v − 4        （无三角形，因此包括每个二分平面图）
g = 5   →   e ≤ 5(v − 2)/3     （没有长度为 3 或 4 的圈）

第一个上界是可以达到的。每个面（包括外部面）都是三角形的平图称为三角剖分；对于三角剖分， 3f = 2e 以等号成立，所以恰好有 e = 3v − 6。八面体（6 个顶点，12 条边）和二十面体（12 个顶点，30 条边）都是三角剖分。向三角剖分添加任何一条边都会使它变成非平面图，所以三角剖分也称为极大平面图。三棱柱不是极大的：它有 9 条边，而上限是 3 × 6 − 6 = 12，在每个四边形面中各加一条对角线，共三条，就能使边数达到 12。

有两个推论会经常用到。第一个是平面图是稀疏的：边数只随顶点数线性增长，所以一个有一百万个顶点的平面图少于三百万条边，而一个有一百万个顶点的一般图可能有将近 5000 亿条边。这就是为什么平面图上的算法只需相对于 v 来衡量，也是为什么邻接表而不是邻接矩阵是自然的存储格式，正如图的表示一文中所讨论的。第二个是度五引理：

每个简单平面图都有一个度至多为 5 的顶点。

度数之和为 2e，而 2e ≤ 6v − 12 在 v ≥ 3时成立，所以平均度数小于 6，必有某个顶点的度不超过 5。只有一个或两个顶点的图平凡地满足这个引理。这个引理是紧的：二十面体的每个顶点的度恰好为 5。它是第 8 节中各个着色定理背后的引擎。

5. 为什么 K₅ 和 K₃,₃ 不是平面图

边数上界把“任何画法都不行”从一个关于无穷多种画法的断言，变成了一行计算。

完全图 K5 满足 v = 5 且 e = 10。5 个顶点的平面图至多有 3 × 5 − 6 = 9 条边，所以 K5 不是平面图。

完全二分图 K3,3 满足 v = 6 且 e = 9。第一个上界允许 12 条边，所以它什么也说明不了。但 K3,3 是二分图，因而没有三角形，而第二个上界只允许 2 × 6 − 4 = 8条边。九条边恰好多了一条。这就是经典的三公用设施谜题，它要求把三栋房子分别连到水、煤气和电，且任何管道或电缆都不交叉。它以“水、煤气和电”（Water, Gas, and Electricity）为题，出现在 Henry Dudeney 的 Amusements in Mathematics （1917）一书中，而二分图指南从二分图的角度给出了同样的论证。

与三棱柱的比较是最有启发的部分。两个图都有六个顶点和九条边，而且每个顶点的度都是 3，所以任何关于顶点数、边数或度数的计数都无法区分它们。区分它们的是面的形状：三棱柱可以利用两个三角形，而 K3,3 需要每个面都至少有四条边，而空间不足以做到这一点。

这两个图都只是勉强不是平面图。如图所示，它们都能画成恰好有一个交叉，所以它们的交叉数为 1。从任一图中删除任意一条边，都会得到平面图。在精确的意义上，它们是平面性的最小障碍，而下一节将说明它们是仅有的障碍。

计数上界有一个必须讲清楚的局限：它们是必要条件，而不是充分条件。违反它们的图肯定不是平面图；满足它们的图仍可能不是平面图。取 K3,3，在同一侧的两个顶点之间加一条边。新图有 6 个顶点和 10 条边，并且现在含有三角形，所以唯一适用的上界是 3v − 6 = 12，而它满足这个上界。然而它包含 K3,3，所以不可能是平面图。 Petersen 图介于两者之间。它有 10 个顶点和 15 条边，同时通过了 3v − 6 = 24 和 2v − 4 = 16，但它的围长是 5，而围长上界只允许 5 × 8 / 3，约为 13.3，即 13 条边。十五条边太多了，所以 Petersen 图不是平面图。

6. Kuratowski 定理与 Wagner 定理

有两种运算把一个图与它内部的小障碍联系起来。一个图的细分是把它的边替换为路径，即沿着边插入新的度为 2 的顶点。细分一条边不会改变画法是否有交叉，因为新顶点只是落在曲线上，所以 K5 或 K3,3 的细分与原图一样不是平面图。平面图也不可能包含非平面子图，因为删除平面画法的一部分后剩下的仍是平面画法。1930 年，Kazimierz Kuratowski 证明了这些显而易见的障碍就是仅有的障碍。

Kuratowski 定理（1930）。一个图是平面图，当且仅当它没有任何子图是 K5 或 K3,3的细分。

“仅当”这一半就是刚才描述的容易方向。“当”这一半才是深刻的：任何不能画在平面上的图都必定包含这两种形状之一，其边可能被拉长成长路径。第二种运算给出一个更简洁的版本。收缩一条边，就是把它的两个端点合并为一个顶点，该顶点与两端原来的所有邻居相邻；从 G 出发，通过删除顶点和边以及收缩边得到的图，称为子式，我们说它是 G的子式。收缩也保持平面性，因为可以把平面画法中的一条边收缩成一个点。

Wagner 定理（1937）。一个图是平面图，当且仅当它既不以 K5 也不以 K3,3 为子式。

这两个定理是等价的，但在例子中并不能互换，Petersen 图展示了其中的区别。把连接其外圈 5-圈与内部五角星的五条辐条收缩，十个顶点就坍缩为五个，每个都与其余四个相邻：Petersen 图有一个 K5 子式。但它并不包含细分的 K5，因为 K5 的细分需要五个度为 4 的顶点，而 Petersen 图的每个顶点的度都是 3。Kuratowski 定理仍然成立，靠的是另一种形状。删除任意一个顶点，剩下的 9 个顶点和 12 条边就构成 K3,3的一个细分：其中三个顶点的度为 2，位于路径上，另外六个分成两组，每组三个。

Wagner 的形式开启了一个大得多的故事。平面性是子式封闭的：平面图的每个子式都是平面图。Neil Robertson 和 Paul Seymour 在 1983 年至 2004 年间发表的一系列论文中证明，每个子式封闭的图族都可以用一个有限的禁止子式列表来刻画，正如平面图由列表 K5、 K3,3来刻画一样。该定理保证这样的列表存在且有限，但并没有说明列表有多长，也没有说明如何找到它。

7. 平面性判定

第 4 节中的计数上界提供了一个即时的初步检验。它们无法证明一个图是平面图，但当它们不成立时就证明了图不是平面图，而且检查它们几乎不花任何代价。下面的函数从每个顶点出发做一次广度优先搜索来计算围长，并应用围长上界，它把 3v − 6 和 2v − 4 都作为特例包含在内。

from collections import deque

def girth(adj):
    """最短圈的长度（森林返回 inf）：从每个顶点各做一次 BFS。"""
    best = float('inf')
    for s in adj:
        dist, parent = {s: 0}, {s: None}
        queue = deque([s])
        while queue:
            u = queue.popleft()
            for w in adj[u]:
                if w not in dist:
                    dist[w], parent[w] = dist[u] + 1, u
                    queue.append(w)
                elif parent[u] != w:         # 非树边闭合一个圈
                    best = min(best, dist[u] + dist[w] + 1)
    return best

def euler_filter(adj):
    """False：肯定不是平面图。True：仅表示“未被排除”。适用于简单连通图。"""
    n = len(adj)
    m = sum(len(ws) for ws in adj.values()) // 2
    g = girth(adj)
    if g == float('inf'):
        return True                          # 树总是平面图
    return m * (g - 2) <= g * (n - 2)        # g = 3 给出 3n - 6，g = 4 给出 2n - 4

def graph(edges):
    adj = {}
    for u, v in edges:
        adj.setdefault(u, []).append(v)
        adj.setdefault(v, []).append(u)
    return adj

prism = graph(['AB', 'BC', 'CA', 'DE', 'EF', 'FD', 'AD', 'BE', 'CF'])
k5 = graph([(i, j) for i in range(5) for j in range(i + 1, 5)])
k33 = graph([(a, b) for a in 'abc' for b in 'xyz'])
petersen = graph([(i, (i + 1) % 5) for i in range(5)] + [(i, i + 5) for i in range(5)]
                 + [(5 + i, 5 + (i + 2) % 5) for i in range(5)])
k33_plus = graph([(a, b) for a in 'abc' for b in 'xyz'] + [('a', 'b')])
for name, adj in [('prism', prism), ('K5', k5), ('K3,3', k33),
                  ('Petersen', petersen), ('K3,3 + edge', k33_plus)]:
    print(f'{name:12} girth {girth(adj)}  passes: {euler_filter(adj)}')
# prism        girth 3  passes: True
# K5           girth 3  passes: False
# K3,3         girth 4  passes: False
# Petersen     girth 5  passes: False
# K3,3 + edge  girth 3  passes: True

这个过滤器拒绝了 K5、 K3,3 和 Petersen 图；它放行了三棱柱，这是正确的，也放行了 K3,3 加一条边后的图，这是错误的。“通过”永远只意味着“未被排除”。每次广度优先搜索需要 O(v + e) 的时间，而过滤器从每个顶点各运行一次，所以总代价为 O(v(v + e))；不满足更便宜的检验 e ≤ 3v − 6 的图，甚至在计算围长之前就可以被拒绝。

完整的答案需要真正的平面性算法。Kuratowski 定理并不能直接给出高效的算法，因为搜索细分的代价很高。Hopcroft 和 Tarjan 于 1974 年发表了第一个线性时间的平面性判定，它建立在深度优先搜索之上；后来的算法使这个思想更容易实现：Boyer 和 Myrvold 2004 年的加边方法，以及 de Fraysseix 和 Rosenstiehl 的左右平面性判据，NetworkX 的实现就基于后者。好的实现无论结果如何都会返回证书：图是平面图时返回一个平面嵌入，不是时返回一个 Kuratowski 子图。

import networkx as nx

def count_faces(embedding):
    seen, f = set(), 0
    for u, v in embedding.edges():           # 每条半边恰好位于一个面上
        if (u, v) not in seen:
            embedding.traverse_face(u, v, mark_half_edges=seen)
            f += 1
    return f

tests = [('prism', nx.circular_ladder_graph(3)), ('K5', nx.complete_graph(5)),
         ('K3,3', nx.complete_bipartite_graph(3, 3)), ('Petersen', nx.petersen_graph()),
         ('K3,3 + edge', nx.complete_bipartite_graph(3, 3))]
tests[-1][1].add_edge(0, 1)
for name, G in tests:
    planar, cert = nx.check_planarity(G, counterexample=True)
    if planar:
        print(f'{name:12} planar, {count_faces(cert)} faces')
    else:
        branch = sum(1 for _, d in cert.degree() if d > 2)
        kind = 'K5' if branch == 5 else 'K3,3'
        print(f'{name:12} not planar: a subdivision of {kind}, '
              f'{cert.number_of_nodes()} vertices, {cert.number_of_edges()} edges')
# prism        planar, 5 faces
# K5           not planar: a subdivision of K5, 5 vertices, 10 edges
# K3,3         not planar: a subdivision of K3,3, 6 vertices, 9 edges
# Petersen     not planar: a subdivision of K3,3, 9 vertices, 12 edges
# K3,3 + edge  not planar: a subdivision of K3,3, 6 vertices, 9 edges

每个答案都附有证明。对于三棱柱，证书是一个以旋转系统形式存储的嵌入，追踪它会得到 5 个面，正如欧拉公式所要求的。对于 K5 和 K3,3，证书就是整个图。对于 Petersen 图，证书是 K3,3 的一个细分，使用了 10 个顶点中的 9 个，正是上图右栏中的结构，而它永远不可能是 K5 的细分，因为没有顶点的度为 4。Kuratowski 子图并不唯一，所以其他库或其他版本可能返回不同的子图；它们中的任何一个都是有效的证明。

8. 平面图着色与四色定理

平面图最著名的定理出现在着色领域。一个正常着色给每个顶点一种颜色，使每条边的两个端点颜色不同；能做到这一点的最少颜色数就是色数，在图着色指南中有深入讨论。给地图着色使相邻国家颜色不同，就是在地图对应的平面图上求解同一个问题，其中每个国家对应一个顶点，每段共同边界对应一条边。

第 4 节的度五引理已经给出了一个有初等证明的上界。

六色定理。每个平面图都可以用至多六种颜色正常着色。

删除一个度至多为 5 的顶点（由引理知它存在），用归纳法给图的其余部分着色，这部分仍是平面图。然后把这个顶点放回去。它至多有五个邻居，所以六种颜色中至少有一种可以给它用。这个证明本身就是一个算法：反复删除度最小的顶点，然后按删除的逆序给顶点着色。

def six_colour(adj):
    """用至多 6 种颜色给简单平面图着色（最小度最后贪心）。"""
    deg = {v: len(ws) for v, ws in adj.items()}
    removed, order = set(), []
    while len(order) < len(adj):
        v = min((u for u in adj if u not in removed), key=deg.get)  # 必存在度 <= 5 的顶点
        removed.add(v)
        order.append(v)
        for w in adj[v]:
            if w not in removed:
                deg[w] -= 1
    colour = {}
    for v in reversed(order):                # 至多 5 个邻居已经着色
        used = {colour[w] for w in adj[v] if w in colour}
        colour[v] = min(c for c in range(6) if c not in used)
    return colour

# 二十面体：12 个顶点，30 条边，每个顶点的度恰好为 5。
edges = []
for i in range(5):
    j = (i + 1) % 5
    top, a, b, c, d, bottom = 0, 1 + i, 1 + j, 6 + i, 6 + j, 11
    edges += [(top, a), (a, b), (a, c), (a, d), (c, d), (c, bottom)]
adj = {v: [] for v in range(12)}
for u, v in edges:
    adj[u].append(v)
    adj[v].append(u)
colour = six_colour(adj)
print(len(edges), {len(ws) for ws in adj.values()}, max(colour.values()) + 1)
# 30 {5} 4
print(all(colour[u] != colour[v] for u, v in edges))
# True

在二十面体上，每个顶点的度恰好为 5，这个方法用了四种颜色，这已是最少的，因为每个顶点和它周围的五个邻居本身就需要四种颜色。这种排序启发式并不总能做得这么好，但它永远不会需要超过六种颜色。

要降到五种颜色还需要一个想法。1879 年，Alfred Kempe 发表了一个“四种颜色总是足够”的证明，其基础是沿着一条颜色交替的顶点链交换两种颜色，这种链如今称为 Kempe 链。1890 年，Percy Heawood 发现了 Kempe 论证中的漏洞，并在同一篇论文中挽救了这种链技术，证明了五种颜色总是足够。这个问题本身可以追溯到 1852 年，当时 Francis Guthrie 注意到四种颜色就足以给英格兰各郡的地图着色，并问这是否总是成立；他的弟弟 Frederick 把这个问题转给了 Augustus De Morgan。

四色定理（Appel 和 Haken，1976）。每个平面图都可以用至多四种颜色正常着色。

Kenneth Appel 和 Wolfgang Haken 于 1976 年宣布了证明，并于 1977 年发表。证明把问题归结为有限个构形，已发表版本中共有 1,482 个，并用计算机逐一检验，耗费约 1,200 小时机时。这是第一个无法用手工检验其证明的重要定理。1997 年，Robertson、Sanders、Seymour 和 Thomas 简化了证明，把构形集合缩减到 633 个；2005 年，Georges Gonthier 在 Coq 证明助手中完成了一个逐行检验的完全形式化证明，消除了对计算机部分的任何残存疑虑。

四是正确的数字： K4 是平面图且需要四种颜色，因为它的四个顶点两两相邻。一般来说三种颜色是不够的，而且判断一个给定的平面图能否用三种颜色着色是 NP 完全的，这是 Garey、Johnson 和 Stockmeyer 在 1976 年证明的，即使每个顶点的度至多为 4 也是如此。反过来，Grötzsch 在 1959 年证明了每个平面图只要不含三角形，就可以 3 着色。最后，两种颜色够用的恰好是二分图，无论它是否为平面图。

9. 对偶图

每个平图 G 都有一个伙伴，即它的对偶图 G*。在 G的每个面内放置一个新顶点。然后，对于 G的每条边，画一条与它相交的对偶边，连接它两侧两个面对应的对偶顶点。如果一条边两侧是同一个面，它的对偶边就是一个自环；共享多条边的两个面由平行的对偶边相连，所以对偶图一般是多重图。

三棱柱有五个面，所以它的对偶图有五个顶点。内三角形 D, E, F 的对偶顶点与三个四边形相连，外部面的对偶顶点也与这三个四边形相连，而三个四边形彼此相连成一个三角形。这个对偶图就是三角双锥，即沿底面粘合在一起的两个三棱锥：5 个顶点、9 条边和 6 个三角形面，三棱柱的 6 个顶点各对应一个面。

对偶交换了顶点与面的角色，而保留了边： G* 有 f 个顶点、 e 条边和 v 个面，所以欧拉公式对两者的形式完全相同。对于连通平图，对偶图的对偶图又是原图。正多面体在对偶下成对出现，立方体与八面体配对，十二面体与二十面体配对，而四面体是它自己的对偶。

对偶把一种结构转化为另一种结构：

• 面着色变成顶点着色。给地图的区域着色使相邻区域颜色不同，等同于给对偶图的顶点着色。地图的四色定理正是这样变成关于平面图的命题的。
• 圈变成割。在 G 中，一个圈的边对应于一个极小的对偶边集合，删除这些边会使 G*不连通，因为这个圈把它内部的面与外部的面分隔开。在平面网络中，这把最小割问题转化为对偶图中的最短圈问题，这也是平面图上的最大流比一般图更快的原因之一（见最大流与最小割）。
• 生成树成对出现。如果 T 是 G的一棵生成树，那么不在 T 中的那些边，其对偶边构成 G*的一棵生成树。对边计数得到 (v − 1) + (f − 1) = e，这又是欧拉公式，只是从一个完全不同的方向得到的。

这个定义附带一个警告。对偶图是由画法而不是由图构造的，所以一个有多种不同嵌入的平面图可能有多个互不同构的对偶图。Whitney 在 1932 年和 1933 年证明，这种情况不会发生在 3-连通平面图上，即删除任意两个顶点后仍保持连通的平面图：它们在球面上的嵌入本质上是唯一的，对偶图也是如此。三棱柱是 3-连通的，所以它的对偶图是良定义的。根据 Steinitz 定理，3-连通平面图也恰好就是凸多面体的图，这又绕回到了 Euler。

10. 平面图出现在哪里

平面性是一种几何性质，所以凡是网络必须布置在某个曲面上的地方，以及曲面被分割成区域的地方，都会出现它。

电路是经典的应用。在单层印刷电路板上，铜导线一旦交叉就会短路，所以连接图必须是平面图。当它不是平面图时，设计者会把一些导线布在第二层上，并通过称为过孔的钻孔连接各层，或者用跳线让一条导线跨过另一条。一个图在任何画法中交叉的最少个数，即它的交叉数，衡量了电路偏离平面的程度，而容纳其全部边所需的平面层数称为它的厚度。

地图是第二个应用。一张国家地图是一个平图，其面就是各个国家，它的对偶图中每个国家对应一个顶点，每段共同边界对应一条边。给国家着色就是给对偶图着色，而四色定理把颜色数的上限定为四，前提是每个国家都是一个连通区域。真实的地图集会打破这个前提：分成几块的国家，例如带有阿拉斯加的美国或带有加里宁格勒的俄罗斯，必须在两个地方使用相同的颜色，而带有这类约束的地图可能需要超过四种颜色。

道路网络与分隔集是第三个应用。Lipton 和 Tarjan 在 1979 年证明，每个有 n 个顶点的平面图都可以分成两部分，每部分都不超过 2n/3 个顶点，而只需删除 O(√n) 个顶点。小分隔集是平面图上分治算法的基础，包括更快的最短路径计算。道路网络并不完全是平面的，因为有桥梁和隧道，但它们通常也能通过删除少量路口被切分成大块，而基于划分的路径规划器正依赖于这一性质。

网格是最后一个应用。一个形状像球面、没有缺口也没有柄的曲面，其闭合三角网格满足 v − e + f = 2，又因为每个三角形有三条边，每条边与两个三角形相邻，所以 3f = 2e。两者合起来迫使 f = 2v − 4 且 e = 3v − 6。这种曲面的网格如果不满足这些计数，就说明某处存在缺口、缺失的三角形或重复的顶点，因此这些计数在导入或修复网格时是一个廉价的合理性检查。

11. 超越平面：交叉与曲面

非平面图并不是故事的终点。有两个自然的问题可以衡量它离平面有多远。

第一个是交叉数 cr(G)，即任何画法中交叉的最少个数。平面图的交叉数为 0，而 K5 和 K3,3 的交叉数为 1。一般情况下计算交叉数是 NP 难的，即使对于完全图，也只在小规模情形下知道精确值。

第二个是换一种曲面来画。环面，即环形甜甜圈的表面，有一个洞，而这个洞让边可以绕开彼此。 K5 和 K3,3 都可以无交叉地画在环面上，而且 K7也可以。欧拉公式可以推广：嵌入在有 g 个洞的曲面上、并使每个面都是圆盘的图，满足

v − e + f = 2 − 2g

平面或球面        g = 0:   v − e + f = 2
环面              g = 1:   v − e + f = 0         环面上的 K7：  7 − 21 + 14 = 0

数 2 − 2g 称为曲面的 Euler 示性数，它是拓扑学中最早的不变量之一。Heawood 在他 1890 年的论文中用它给出了在有 g 个洞的曲面上所需颜色数的上界，而这个上界对每个 g ≥ 1 都是精确的，由 Ringel 和 Youngs 于 1968 年证明。对环面而言答案是 7，而 K7 表明确实可能需要七种颜色。平面的情形，即同一公式会给出 4 的情形，是他们的工作唯一没有覆盖的情形；那就是四色定理。

12. 常见错误

13. 术语表

15. 参考文献

以上定义、定理和归属均出自以下文献，按时间顺序排列。

1. Euler, L. (1758). "Elementa doctrinae solidorum." Novi Commentarii Academiae Scientiarum Petropolitanae 4 (1752/53)，109 至 140 页。多面体公式，陈述时未给证明。
2. Euler, L. (1758). "Demonstratio nonnullarum insignium proprietatum, quibus solida hedris planis inclusa sunt praedita." Novi Commentarii Academiae Scientiarum Petropolitanae 4 (1752/53)，140 至 160 页。Euler 通过切去角给出的证明。
3. Legendre, A.-M. (1794). Éléments de géométrie. 巴黎。第一个完整证明，借助球面多边形。
4. Cauchy, A.-L. (1813). "Recherches sur les polyèdres. Premier mémoire." Journal de l'École Polytechnique 9 (16e cahier)，68 至 86 页。
5. Kempe, A. B. (1879). "On the Geographical Problem of the Four Colours." American Journal of Mathematics 2(3)，193 至 200 页。
6. Heawood, P. J. (1890). "Map-Colour Theorem." Quarterly Journal of Pure and Applied Mathematics 24，332 至 338 页。Kempe 证明中的漏洞、五色定理，以及其他曲面上的上界。
7. Dudeney, H. E. (1917). Amusements in Mathematics. 伦敦：Thomas Nelson。第 251 题，“Water, Gas, and Electricity”。
8. Steinitz, E. (1922). "Polyeder und Raumeinteilungen." In Encyklopädie der mathematischen Wissenschaften，第 3 卷（Geometrie），第 3AB12 部分，1 至 139 页。莱比锡：Teubner。
9. Kuratowski, K. (1930). "Sur le problème des courbes gauches en topologie." Fundamenta Mathematicae 15，271 至 283 页。
10. Whitney, H. (1932). "Non-separable and Planar Graphs." Transactions of the American Mathematical Society 34(2)，339 至 362 页。组合对偶。
11. Whitney, H. (1933). "2-Isomorphic Graphs." American Journal of Mathematics 55，245 至 254 页。3-连通平面图嵌入的唯一性。
12. Wagner, K. (1936). "Bemerkungen zum Vierfarbenproblem." Jahresbericht der Deutschen Mathematiker-Vereinigung 46，26 至 32 页。直线画法。
13. Wagner, K. (1937). "Über eine Eigenschaft der ebenen Komplexe." Mathematische Annalen 114，570 至 590 页。用禁止子式刻画平面性。
14. Fáry, I. (1948). "On Straight Line Representation of Planar Graphs." Acta Scientiarum Mathematicarum (Szeged) 11，229 至 233 页。
15. Grötzsch, H. (1959). "Zur Theorie der diskreten Gebilde, VII: Ein Dreifarbensatz für dreikreisfreie Netze auf der Kugel." Wissenschaftliche Zeitschrift der Martin-Luther-Universität Halle-Wittenberg, Mathematisch-Naturwissenschaftliche Reihe 8，109 至 120 页。
16. Ringel, G. and Youngs, J. W. T. (1968). "Solution of the Heawood Map-Coloring Problem." Proceedings of the National Academy of Sciences 60(2)，438 至 445 页。
17. Hopcroft, J. and Tarjan, R. (1974). "Efficient Planarity Testing." Journal of the ACM 21(4)，549 至 568 页。
18. Garey, M. R., Johnson, D. S. and Stockmeyer, L. (1976). "Some Simplified NP-Complete Graph Problems." Theoretical Computer Science 1(3)，237 至 267 页。平面图的 3 着色问题是 NP 完全的。
19. Lakatos, I. (1976). Proofs and Refutations: The Logic of Mathematical Discovery. J. Worrall 和 E. Zahar 编。剑桥：Cambridge University Press。
20. Appel, K. and Haken, W. (1977). "Every Planar Map is Four Colorable. Part I: Discharging." Illinois Journal of Mathematics 21(3)，429 至 490 页。
21. Appel, K., Haken, W. and Koch, J. (1977). "Every Planar Map is Four Colorable. Part II: Reducibility." Illinois Journal of Mathematics 21(3)，491 至 567 页。
22. Lipton, R. J. and Tarjan, R. E. (1979). "A Separator Theorem for Planar Graphs." SIAM Journal on Applied Mathematics 36(2)，177 至 189 页。
23. Federico, P. J. (1982). Descartes on Polyhedra: A Study of the De Solidorum Elementis. 纽约：Springer。Descartes 的手稿与 Leibniz 的抄本。
24. de Fraysseix, H. and Rosenstiehl, P. (1985). "A Characterization of Planar Graphs by Trémaux Orders." Combinatorica 5(2)，127 至 135 页。左右判据。
25. Robertson, N., Sanders, D. P., Seymour, P. and Thomas, R. (1997). "The Four-Colour Theorem." Journal of Combinatorial Theory, Series B 70(1)，2 至 44 页。
26. Boyer, J. M. and Myrvold, W. J. (2004). "On the Cutting Edge: Simplified O(n) Planarity by Edge Addition." Journal of Graph Algorithms and Applications 8(3)，241 至 273 页。
27. Robertson, N. and Seymour, P. D. (2004). "Graph Minors. XX. Wagner's Conjecture." Journal of Combinatorial Theory, Series B 92(2)，325 至 357 页。
28. Gonthier, G. (2008). "Formal Proof: The Four-Color Theorem." Notices of the American Mathematical Society 55(11)，1382 至 1393 页。
29. Bondy, J. A. and Murty, U. S. R. (2008). Graph Theory. Graduate Texts in Mathematics 244。Springer。第 10 章和第 11 章讨论平面图与四色问题。
30. Diestel, R. (2017). Graph Theory，第 5 版。Graduate Texts in Mathematics 173。柏林：Springer。第 4 章讨论平面图。