上次我们谈到当$n \geq 5$时，完全图$K_n$不是平面图。现在我们将致力于证明这一点。

一些概念

平面图(planar graph)：如果一个图可以被绘制在平面上，并且其边仅在顶点处相交，那么这个图就是平面图。
完全图(complete graph)：一个完全图$K_n$是一个简单图，其中每对不同的顶点之间都恰好有一条边。
二分图(bipartite graph)：一个二分图是一个图，其顶点集合可以被划分为两个不相交的子集$U$和$V$，使得图中的每条边都连接一个来自$U$的顶点和一个来自$V$的顶点。
面(faces)：在平面图中，边界由边和顶点组成的区域被称为面(face)。每个面都是一个闭合的区域，可以是有限的也可以是无限的。

根据上面的定义，二分图是指其顶点集合可以被划分为两个不相交的子集$U$和$V$，使得图中的每条边都连接一个来自$U$的顶点和一个来自$V$的顶点。换句话说，在二分图中不存在连接同一子集内两个顶点的边。例如，考虑下面的图：

  A
 / \
B   C
 \ /
  D

在这个图中，我们可以将顶点集合划分为$U = {A, D}$和$V = {B, C}$，使得每条边都连接一个来自$U$的顶点和一个来自$V$的顶点。因此，这个图是一个二分图，我们可以将其称为$K_{2,2}$，因为它是一个完全二分图，其中$U$和$V$分别有两个顶点。显然，$K_{2,2}$是一个平面图，因为我们可以在平面上绘制它而不使边相交。那么$K_{3,3}$呢？$K_{3,3}$是一个完全二分图，其中$U$和$V$分别有三个顶点。我们可以尝试在平面上绘制$K_{3,3}$，但是无论我们如何尝试，我们都会发现至少有两条边相交。我们有理由相信，$K_{3,3}$不是一个平面图。下面，我们也将证明这一点。

欧拉公式(Euler’s formula)

对于一个连通的平面图，欧拉公式表明顶点数$V$、边数$E$和面数$F$之间满足以下关系：
$$V + F = E + 2$$
这个公式是由瑞士数学家莱昂哈德·欧拉在18世纪提出的。它揭示了平面图的基本结构，并且在证明平面图的一些性质时非常有用。
至于如何证明，此处先略去不谈。

证明$K_5$不是平面图

假设$K_5$是一个平面图，那么它必须满足欧拉公式。对于$K_5$，我们有$V = 5$和$E = 10$。将这些值代入欧拉公式，我们得到：
$$5 + F = 10 + 2$$
因此，面数$F$必须等于7。然而，在一个平面图中，每条边至多属于两个不同的面（因为边界必须由边和顶点组成），而每个面至少由三条边组成，所以我们有以下不等式：
$$2E \geq 3F$$
将$E = 10$和$F = 7$代入这个不等式，我们得到：
$$20 \geq 21$$
这是一个矛盾，因此我们的假设是错误的。由此我们得出结论：$K_5$不是一个平面图。

证明$K_{3,3}$不是平面图

这个证明其实与上面类似。对于$K_{3,3}$，我们有$V = 6$和$E = 9$。将这些值代入欧拉公式，我们得到：
$$6 + F = 9 + 2$$
因此，面数$F$必须等于5。但是在这样一个二分图中，每条边至少属于两个不同的面（因为边界必须由边和顶点组成），而每个面至少由四条边组成（因为二分图中不存在连接同一子集内两个顶点的边，所以每个面至少需要四条边才能形成一个闭合区域），所以我们有以下不等式：
$$2E \geq 4F$$
将$E = 9$和$F = 5$代入这个不等式，我们得到：
$$18 \geq 20$$
这是一个矛盾，因此我们的假设是错误的。由此我们得出结论：$K_{3,3}$不是一个平面图。

上面的两个证明是同一个套路，即欧拉公式+边-面邻接关系从而得出矛盾。我们可以总结出一个结论：如果一个图$G$是一个平面图，那么$G$必须满足以下不等式：
$$E \leq 3V - 6$$
如果$G$是一个二分图，那么$G$必须满足以下不等式：
$$E \leq 2V - 4$$

一个定理

定理：一个图$G$是一个平面图的充分必要条件是$G$中不存在$K_5$或$K_{3,3}$的子图。

这个定理的一个方向已经被我们证明了，但是另一个方向却没有那么容易。这个定理被称为**库拉托夫斯基定理(Kuratowski’s theorem)**。其证明相当困难，这里有一个证明，得日后再研究了。

欧拉公式的证明：数学归纳法

看了上面的两个证明，可以感受到欧拉公式的威力。现在我们来证明欧拉公式。我们使用数学归纳法来证明这个结论。

基础情况：当$V = F = 1, E = 0$时，欧拉公式成立。
归纳假设：假设对于任意一个连通的平面图$G$，如果$G$是一个树，根据前面树的性质，我们知道$E = V - 1$，并且$F = 1$（因为树只有一个面，即整个平面），所以欧拉公式成立。而如果$G$中至少存在一个环，那么我们可以找到一个环$C$，并且去掉这个环上的一条边$e$，得到一个新的图$G’$。根据归纳假设，$G’$满足欧拉公式，即$V’ + F’ = E’ + 2$。
归纳步骤：现在我们来分析$G$和$G’$之间的关系。因为我们去掉了一个环上的一条边$e$，所以$E’ = E - 1$。同时，去掉这条边$e$会将环$C$分成两个面，因此$F’ = F - 1$。而顶点数$V$没有改变，所以$V’ = V$。将这些关系代入欧拉公式，我们得到：
$$V’ + F’ = E’ + 2$$
$$V + (F - 1) = (E - 1) + 2$$
$$V + F - 1 = E + 1$$
$$V + F = E + 2$$
因此，$G$也满足欧拉公式。通过数学归纳法，我们证明了对于任意一个连通的平面图，欧拉公式都成立。

端点染色

染色问题就是指用多少种不同的颜色给图的顶点着色，使得相邻顶点的颜色不同。实际上，任何端点染色问题都可以一一映射为一个图的着色问题。我们可以将每个端点看作一个顶点，将每条边看作连接两个顶点的边，那么端点染色问题就转化为了图的着色问题。而端点染色问题和上面提到的平面图、完全图和树等概念密切相关。我们可以用手画几张图感受一下染色的过程。

六色定理

首先，任何一张平面图，用六种颜色就一定可以完成端点染色。这个问题等价于将平面图中的所有点分成六类，使得每类中的点之间没有边相连（也可以说是一种“六分图”）。我们来证明这个论断。
假设我们有一个平面图$G$，我们可以使用欧拉公式来分析这个图的结构。根据欧拉公式，我们知道对于一个连通的平面图，顶点数$V$、边数$E$和面数$F$满足以下关系：
$$V + F = E + 2$$
同时，我们还知道在一个平面图中，每条边属于两个不同的面，而每个面至少由三条边组成，所以我们有以下不等式：
$$2E \geq 3F$$
将这个不等式代入欧拉公式，我们得到：
$$3V + 3F = 3E + 6 \leq 2E + 6$$
$$E \leq 3V - 6$$
这张图的总度数是$2E$，所以平均度数是$\frac{2E}{V} \leq \frac{6V - 12}{V} = 6 - \frac{12}{V}$。因此，至少存在一个顶点的度数不超过5。我们可以将这个顶点染成第一种颜色，然后将与这个顶点相邻的顶点染成第二种颜色。接下来，我们可以将与第二种颜色相邻的顶点染成第三种颜色，以此类推，直到我们使用了六种颜色为止。然后，将这个点移除/忽略，继续对剩下的图进行染色。通过这种方式，我们可以确保相邻的顶点不会被染成同一种颜色，因此我们可以使用六种颜色完成端点染色。

五色定理

接下来，我们可以观察到，对于一个有五条边连接的中心点来说，如果它的其中两个不同颜色的邻居之间存在一条仅由这两种颜色的连通分量（也就是一张子图）相连，那么我们可以交换这个子图中的两种颜色，使之仍然是一个有效的染色图。也就是说，如果这样的子图中间存在断点将其分成两半，那么我们可以将其中一个邻居的那半个连通分量上的互换颜色，从而为中心点腾出一个颜色，这样我们就可以少用一种颜色来完成染色。通过这种方式，我们可以将需要的颜色数减少到五种。
接下来，我们来证明，对于一个有五条边的中心顶点来说，最差的情况是它们已经用完五种颜色了，这时需要我们通过变换其中一个邻居的颜色来为中心点腾出一种颜色。假设我们有一个中心顶点$C$，它有五个邻居$N_1, N_2, N_3, N_4, N_5$，每个邻居都被染成了不同的颜色。我们可以观察到，如果存在一个仅由两种颜色组成的连通分量连接了其中两个邻居，例如$N_1$和$N_2$，那么这两种颜色就无法通过交换来为中心点$C$腾出一个颜色，因为交换后$N_1$和$N_2$仍然会占用两种不同的颜色。而对于$N_3$和$N_4$，如果它们之间同样存在一个仅由两种颜色组成的连通分量，那么交换后$N_3$和$N_4$仍然会占用两种不同的颜色。但同时存在两个这样的连通分量是不可能的，因为如果存在，那么根据平面图的要求，这两个连通分量之间必然相交，相交的那个点需要同时染成$N_1$或$N_2$的颜色和$N_3$或$N_4$的颜色，一个点不能染成两种颜色，因此矛盾。因此，至少存在一个邻居的颜色可以通过交换来为中心点$C$腾出一个颜色，从而使得我们只需要五种颜色来完成染色。

超立方体

定义

超立方体(hypercube)是一个立方体，每个点代表一个由0和1组成的字符串，每条边连接两个字符串之间仅有一个位置不同的点。例如，三维超立方体（也称为立方体）有8个顶点，分别是000、001、010、011、100、101、110和111。每条边连接两个顶点，这些顶点之间仅有一个位置不同，例如000和001之间有一条边，因为它们在最后一个位置上不同；而000和110之间则没有边，因为它们有两个位置都不同。
还有一种使用递归的定义方式，任意一个$n$维超立方体$Q_n$可以通过将两个$(n-1)$维超立方体$Q_{n-1}$连接起来构造出来。具体来说，我们可以将一个$(n-1)$维超立方体的每个顶点与另一个$(n-1)$维超立方体的对应顶点连接起来，从而形成一个新的$n$维超立方体。例如，二维超立方体（也称为正方形）可以通过连接两个一维超立方体（线段）来构造出来；三维超立方体（也称为立方体）可以通过连接两个二维超立方体（正方形）来构造出来，以此类推。此外，我们规定$Q_0$是一个单点图，即一个只有一个顶点和没有边的图。

性质

对于$Q_n$：
- 顶点数：$V_n = 2^n$
- 边数：$E_n = 2E_{n-1} + 2^{n-1} = n \cdot 2^{n-1}$
- 每个顶点的度数：$n$
- 面数：$F_n = 2^n - n \cdot 2^{n-1} + 1$

连通性

很明显，$Q_n$是一个连通图，而且连通性相当强。为了描述它的连通性，我们有如下定理：

定理：对于$Q_n = {V_n, E_n}$，如果$S \subseteq V_n$且$|S| \leq |V_n - S|$（即$|S| \leq 2^{n-1}$），记$E_S$为$S$和$V_n - S$之间的边的集合，即$E_S = {(u,v) \in E_n | u \in S, v \in V_n - S}$，那么$|E_S| \geq |S|$。

证明：我们使用数学归纳法来证明这个定理。

基础情况：当$n = 1$时，$Q_1$是一个线段图，对于其子集$S$满足$|S| < 2^{0} = 1$，即$S$只能是包含一个点的集合，此时$|E_S| = 1 \geq |S|$，基础情况成立。
归纳假设：假设对于$Q_{n-1}$，定理成立，即对于任意子集$S’ \subseteq V_{n-1}$，如果$|S’| < 2^{n-2}$，则$|E_{S’}| \geq |S’|$。
归纳步骤：为了便于利用假设，我们将$Q_n$看作是由两个$Q_{n-1}$连接而成的图。设这两个$Q_{n-1}$分别为$Q_{n-1}^0$和$Q_{n-1}^1$，其中$Q_{n-1}^0$的顶点集合为${(x_1, x_2, …, x_{n-1}, 0) | x_i \in {0, 1}}$，$Q_{n-1}^1$的顶点集合为${(x_1, x_2, …, x_{n-1}, 1) | x_i \in {0, 1}}$。每个顶点$(x_1, x_2, …, x_{n-1}, 0)$与对应的顶点$(x_1, x_2, …, x_{n-1}, 1)$之间有一条边连接。这时，我们记
$$S_0 = S \cap V_{n-1}^0$$
$$S_1 = S \cap V_{n-1}^1$$
，其中$V_{n-1}^0$和$V_{n-1}^1$分别是$Q_{n-1}^0$和$Q_{n-1}^1$的顶点集合。由于$S_1$和$S_0$的大小不确定，我们需要考虑两种情况：
1. 如果$|S_0| < 2^{n-2}$且$|S_1| < 2^{n-2}$，根据归纳假设，我们有$|E_{S_0}| \geq |S_0|$和$|E_{S_1}| \geq |S_1|$。同时，由于每个顶点$(x_1, x_2, …, x_{n-1}, 0)$与对应的顶点$(x_1, x_2, …, x_{n-1}, 1)$之间有一条边连接，因此实际删去的边数不小于分别从两个集合中删去的边数，即
  $$|E_S| \geq |E_{S_0}| + |E_{S_1}| \geq |S_0| + |S_1| = |S|$$
2. 如果$|S_0| \geq 2^{n-2}$，由于$|S| < 2^{n-1}$，我们有$|S_1| < 2^{n-2}$。根据归纳假设，我们有$|E_{S_1}| \geq |S_1|$。遗憾的是，我们不能直接对$S_0$应用归纳假设，但是$V_{n-1}^0 - S_0$呢？很明显，因为$|V_{n-1}^0| = 2^{n-1}$，所以$|V_{n-1}^0 - S_0| = 2^{n-1} - |S_0| < 2^{n-2}$，所以我们可以对$V_{n-1}^0 - S_0$应用归纳假设，得到$|E_{V_{n-1}^0 - S_0}| \geq |V_{n-1}^0 - S_0|$。同时，我们知道将$|S_0|$个点从$Q_{n-1}^0$中删去的边数与将$|V_{n-1}^0 - S_0|$个点从$Q_{n-1}^0$中删去的边数相同，因为每条边连接的两个顶点分别来自$S_0$和$V_{n-1}^0 - S_0$，所以我们有
  $$|E_S| \geq |E_{S_1}| + |E_{V_{n-1}^0 - S_0}| \geq |S_1| + |V_{n-1}^0 - S_0| = |S_1| + (2^{n-1} - |S_0|)$$
  但是这还不够，我们需要进一步考虑交叉边，即连接$S_0$和$S_1$之间的边。由于每个顶点$(x_1, x_2, …, x_{n-1}, 0)$与对应的顶点$(x_1, x_2, …, x_{n-1}, 1)$之间有一条边连接，因此至少有$|S_0| - |S_1|$条边连接$S_0$和$S_1$，所以上面的不等式可以更加精确：
  $$|E_S| \geq |E_{S_1}| + |E_{V_{n-1}^0 - S_0}| + (|S_0| - |S_1|) \geq |S_1| + (2^{n-1} - |S_0|) + (|S_0| - |S_1|) = 2^{n-1} \geq |S|$$
  因此，在两种情况下，我们都得到了$|E_S| \geq |S|$，完成了归纳步骤。

对偶图

对于一张超立方体$Q_n$，我们将其每个面看作一个顶点，每条边对应两个面之间的边界，那么我们就得到了$Q_n$的一个对偶图(dual graph)。多画几张图，我们会发现超立方体的对呕图都是平面图。对偶图的每个点度数均为$n+1$，因此它不是二分图。
一般的，对于一个平面图$G$，我们可以通过将每个面看作一个顶点，每条边对应两个面之间的边界来构造$G$的对偶图$G^*$。如果$G$是一个平面图，那么$G^*$也是一个平面图，并且满足以下关系：

$V(G^*) = F(G)$
$E(G^*) = E(G)$
$F(G^*) = V(G)$
因此，$G$和$G^*$之间存在一种对偶关系，即$G$中的顶点对应于$G^*$中的面，$G$中的边对应于$G^*$中的边，$G$中的面对应于$G^*$中的顶点。

更多图论