10.7 平面图

若可以在平面中画出一个图而边没有任何交叉（其中边的交叉时表示边的直线或弧线在它们的公共端点以外的地方相交），则这个图是平面图。这种画法称为这个图的平面表示。

简单来说就是将原来的图采用平面图的形式表示，并且其中的边不交叉。比如下面这张图：

采用平面图表示后如下所示：

欧拉公式

设G是带e条边和u个顶点的连通平面简单图。设r是G的平面图表示中的面数，则r=e-u+2。

比如上面的例子中：

这里解释一下r=6的由来：

证明就算了，直接拿过来用吧。

推论1：

若G是e条边和u个顶点的连通平面简单图，其中u>=3，则e<=3u-6

证明： $$ 根据握手定理：2e=\sum_{u \in U}deg(u) \ 因为至少3条边组成一个面，所以 \sum_{u \in U}deg(u) \geq 3r，即 2e \geq 3r\ 再套用到欧拉公式中，用e和u替换r，最终结果为\ e \leq 3u-6 $$ 推论2:

若G是连通平面简单图，则G中有度数不超过5的顶点。

证明： $$ 假设G中没有度数不超过5的顶点，即每个顶点的最小度数为6。\ 根据握手定理：2e=\sum_{u \in U}deg(u)，所以 2e \geq 6u，即 e \geq 3u，结合推论1，就可以知道这是不可能的。\ 所以原命题为真。 $$ 推论3:

若连通平面简单图有e条边和u个顶点，u>=3，并且每个顶点的度至少为4，那么 e<=2u-4

证明很简单，还是老套路，用握手定理确定边与顶点的关系，然后用欧拉公式替换其中的r参数。

书上说可以用这个来判断一个图是否为平面图。比如k3.3所代表的完全二分图：

本来用欧拉公式就可以了，但是奈何面数太难数了，而且之所以不用推论1，是因为在推论1下它是成立的，所以用推论3。

不用管他书上的一堆名词解释，简单来说就是如果一个图中包含K5和K3.3的话，那么它就不是平面图。

比如下面这张图中就包含了K3.3：

其中藏的k3.3就是如下所示：

所以它不是平面图。