设A为平面图G的顶点集合，B是满足以下条件的最小颜色集合：每个顶点可分配B中的一种颜色，且相邻顶点颜色互不相同。现需以大O记号给出|B|的尽可能紧的上界。请问该上界是否为O(2ⁿ)？我对此类问题不熟悉，不知应从何处着手求解，曾粗略阅读过计算几何、数据结构相关内容。

嘿，这个问题其实有个非常经典的结论，完全不用考虑O(2ⁿ)这么松散的上界！

核心结论 #

这个上界绝对不是O(2ⁿ)，甚至连线性的O(n)都不是——平面图的着色有个鼎鼎大名的四色定理！

任何平面图都可以用最多4种颜色完成合法着色（相邻顶点颜色不同），也就是说不管你的平面图有多少个顶点（n个），最小颜色集合B的大小的上界是常数4，用大O记号表示就是O(1)，这比你问的O(2ⁿ)紧得不是一点半点。

为什么O(2ⁿ)完全不沾边？ #

O(2ⁿ)是指数级增长的复杂度，一般出现在没有特殊结构的图或者极端情况里，但平面图有严格的结构限制：它能嵌入平面且边不交叉。这种结构带来了极强的着色性质——完全不需要随顶点数指数增长的颜色数。
举个反例，完全图Kₙ需要n种颜色，但当n≥5时，完全图根本不是平面图，所以这种极端情况和我们的问题无关。

入门着手方向 #

如果你刚接触这类问题，可以按这个路径走：

• 先搞懂图着色的基本定义，明确合法着色的要求，区分平面图和一般图的本质差异；
• 先学五色定理——它比四色定理容易证明，用归纳法就能推导，而它的证明核心依赖平面图的欧拉公式（n - m + f = 2，n是顶点数，m是边数，f是面数），从欧拉公式能推出平面图里一定存在度数≤5的顶点，这是着色推导的关键；
• 之后再去了解四色定理的相关内容，它是经过计算机辅助证明的经典结论，现在已经被广泛认可。

另外你提到的计算几何和数据结构，平面图的着色问题核心属于图论范畴，但计算几何里的平面嵌入、平面划分等内容和它有一定关联，数据结构可能会涉及平面图的存储和遍历，但解决这个着色上界问题的核心还是图论中的着色理论。

内容的提问来源于stack exchange，提问作者Harry