本节对应原书 PDF 第 164–181 页。定义、定理、公式、例题及其原解答逐字取自原书；解释性文字为 AI 通俗化改写；标有「解读」的引用块为 AI 补充的额外直觉。
在本节将介绍二部图、欧拉图、哈密顿图和平面图.
6.4.1 二部图
今有 4 个工人 a_1,a_2,a_3,a_4，4 项任务 b_1,b_2,b_3,b_4. 已知工人 a_1 熟悉任务 b_1,b_2,b_3；a_2 熟悉 b_2,b_3；a_3 只熟悉 b_4；a_4 熟悉 b_3 和 b_4. 问如何分配任务，才能使每人都有一项自己熟悉的任务，且每项任务都有一人来完成？其实，只要以 V=\{a_1,a_2,a_3,a_4,b_1,b_2,b_3,b_4\} 为顶点集，若 a_i 熟悉 b_j，就在 a_i 与 b_j 之间连边，得边集 E，构成无向图 G=\langle V,E\rangle，如图 6.19 所示.
由图显而易见，分配 a_1 去完成 b_1，a_2 去完成 b_2，a_3 去完成 b_4，a_4 去完成 b_3 就能满足要求.
现在来分析图 6.19. 在此图中，a_1,a_2,a_3,a_4 彼此不相邻，b_1,b_2,b_3,b_4 也彼此不相邻. 像这样的图，称它为二部图. 下面给出它的严格定义. 在本节我们只讨论无向图.
定义 6.19 若能将无向图 G=\langle V,E\rangle 的顶点集 V 分成两个不相交的子集 V_1 和 V_2（即 V_1\cap V_2=\varnothing 且 V_1\cup V_2=V），使得 G 中任何一条边的两个端点一个属于 V_1，另一个属于 V_2，则称 G 为二部图（有的书上称其为偶图、双图，或二分图），V_1,V_2 称为互补顶点子集. 若 G 是二部图，常将 G 记为 G=\langle V_1,V_2,E\rangle，其中 V_1,V_2 是互补顶点子集. 由定义可以看出，n 阶零图（含平凡图）都是二部图.
又若 V_1 中任一顶点与 V_2 中任一顶点均有且仅有一条边相关联，则称二部图 G 为完全二部图. 若 |V_1|=r，|V_2|=s，则记完全二部图为 K_{r,s}.
图 6.20(a) 为 K_{2,3}，图 6.20(b) 为 K_{3,3}.
在完全二部图 K_{r,s} 中，它的顶点数 n=r+s，边数 m=r\cdot s.
定理 6.7 无向图 G=\langle V,E\rangle 是二部图当且仅当 G 中无奇数长度的回路.
证明 必要性. 已知 G=\langle V_1,V_2,E\rangle 为二部图，要证明 G 中无奇数长度的回路. 若 G 中无回路，结论显然成立. 若 G 中有回路，设 C 为一条回路，C=v_{i_1}v_{i_2}\cdots v_{i_l}v_{i_1}，l\geqslant 2. 不妨设 v_{i_1}\in V_1，则 v_{i_1},v_{i_3},\cdots,v_{i_{l-1}}\in V_1，v_{i_2},v_{i_4},\cdots,v_{i_l}\in V_2. 显然 l 为偶数，而 C 的长度为 l，所以 C 为偶圈.
充分性. 已知 G 中无奇数长的回路，要证明 G 是二部图. 若 G 是零图，结论显然成立. 下面不妨设 G 是连通图. 设 v_0 为 G 中任一顶点，令
则 V_1\neq\varnothing，V_2\neq\varnothing，且 V_1\cap V_2=\varnothing，V_1\cup V_2=V. 只要证明 V_1 中任二顶点不相邻，V_2 中的任二顶点也不相邻. 否则，必存在 v_i,v_j\in V_1（或它们属于 V_2），使得边 e=(v_i,v_j)\in E. 设 v_0 到 v_i 和 v_j 的短程线分别为 \Gamma_1 和 \Gamma_2，则 \Gamma_1 和 \Gamma_2 的长度均为偶数（或均为奇数）. 于是 \Gamma_1\cup e\cup\Gamma_2 是 G 中奇数长的回路，这与已知矛盾. 所以 G 是二部图.
由定理 6.7 可知，图 6.21(a) 和 (f) 不是二部图，因为它们中均含奇数长的回路. 而图 6.21(b),(c),(d) 和 (e) 均为二部图，每个图中实心点集 V_1 和空心点集 V_2 都是互补顶点子集. 在画图时，通常将 V_1 放在图的上方，V_2 放在图的下方，这 4 个图分别画成图 6.21(b'),(c'),(d'),(e') 所示的样子，称为标准形式.
定义 6.20 设二部图 G=\langle V_1,V_2,E\rangle，E'\subseteq E. 若 E' 中的边互不相邻，则称 E' 是 G 的匹配. 如果在 E' 中再添加任意一条边后所得到的边子集不再是匹配，则称 E' 是 G 的极大匹配. G 中边数最多的匹配称为 G 的最大匹配.
又设 |V_1|\leqslant|V_2|，E' 是 G 的匹配. 若 |E'|=|V_1|，则称 E' 是 V_1 到 V_2 的完备匹配. 当 |V_1|=|V_2| 时，完备匹配称为完美匹配.
在图 6.22 中，图 6.22(a) 和图 6.22(b) 中的实线边是完备匹配，而图 6.22(c) 中的实线边是最大匹配，但不是完备匹配.
解读：二部图的关键不是「图长什么样」，而是「能不能把顶点二染色，使每条边两端异色」。定理 6.7 把这件事翻译成「没有奇圈」——因为沿偶圈走一圈正好回到同色，沿奇圈走一圈会要求同色却异色。匹配部分则是在问「能不能让 V_1 里每个人都配到人」，完备匹配是「一个不剩」，最大匹配只是「尽量多」。
下述定理给出二部图有完备匹配的充分必要条件.
定理 6.8（Hall 定理） 设二部图 G=\langle V_1,V_2,E\rangle，其中 |V_1|\leqslant|V_2|，则 G 中存在 V_1 到 V_2 的完备匹配当且仅当 V_1 中任意 k(k=1,2,\cdots,|V_1|) 个顶点至少与 V_2 中的 k 个顶点相邻.
定理中的条件常称为"相异性条件".
定理的必要性显然，充分性的证明从略.
图 6.22(c) 中，上面有两个顶点只与下面的一个顶点相邻，不满足相异性条件，因而图 6.22(c) 不存在完备匹配.
定理 6.9 设二部图 G=\langle V_1,V_2,E\rangle，其中 |V_1|\leqslant|V_2|. 如果存在正整数 t，使得 V_1 中每个顶点至少关联 t 条边，而 V_2 中每个顶点至多关联 t 条边，则 G 中存在 V_1 到 V_2 的完备匹配.
这个条件称作 t 条件.
证明 V_1 中任意 k(1\leqslant k\leqslant|V_1|) 个顶点至少关联 kt 条边，而 V_2 中每个顶点至多关联 t 条边，所以这 kt 条边至少关联 V_2 中 k 个顶点，故 V_1 中任意 k 个顶点至少与 V_2 中的 k 个顶点相邻. 由 Hall 定理，G 中存在从 V_1 到 V_2 的完备匹配.
Hall 定理中的相异性条件是二部图存在完备匹配的充分必要条件，而 t 条件只是二部图有完备匹配的充分条件，而不是必要条件. 在图 6.22 中，(a) 不满足 t 条件，但有完备匹配.
例 6.12 某中学有 3 个课外活动小组：数学组，计算机组和生物组. 今有赵、钱、孙、李、周 5 名学生. 已知：
（1）赵、钱为数学组成员，赵、孙、李为计算机组成员，孙、李、周为生物组成员；
（2）赵为数学组成员，钱、孙、李为计算机组成员，钱、孙、李、周为生物组成员；
（3）赵为数学组和计算机组成员，钱、孙、李、周为生物组成员.
问在以上 3 种情况下，能否选出 3 名不兼任的组长？
解 用 v_1,v_2,v_3 分别表示数学组、计算机组和生物组. u_1,u_2,u_3,u_4,u_5 分别表示赵、钱、孙、李、周. 若 u_i 是 v_j 的成员，就在 u_i 与 v_j 之间连边. 每种情况都对应一个二部图，见图 6.23 所示.
记 V_1=\{v_1,v_2,v_3\}，V_2=\{u_1,u_2,u_3,u_4\}. 选 3 名不兼任的组长就是在对应的二部图中求 V_1 到 V_2 的完备匹配. (a) 满足 t 条件，其中 t=2，(b) 满足相异性条件，都存在 V_1 到 V_2 的完备匹配. 因此，对于(1)和(2)可以选出 3 名不兼任的组长. 不难给出这样的方案，而且有多种方案. 例如，对于(1)，赵当数学组长，孙当计算机组组长，李当生物组组长. 这对应于(a)中取匹配 \{(v_1,u_1),(v_2,u_3),(v_3,u_4)\}. (c) 中 v_1 和 v_2 只与 u_1 相邻，不满足相异性条件. 根据 Hall 定理，不存在 V_1 到 V_2 的完备匹配，因此不可能选出 3 名不兼任的组长. 事实上，数学组和计算机组只有赵一人，如果要求不兼任，赵只能当其中一个组的组长，没有第二个人来任另一个组的组长.
解读：Hall 定理的相异性条件是「充要」的，t 条件只是「充分」的——这决定了做题时的用法：要否定完备匹配的存在，只需找到一小组人「朋友太少」；要肯定它存在，用 t 条件往往比逐个验证相异性条件快。例 6.12 三种情形恰好各命中一种判定路径。
6.4.2 欧拉图
18 世纪，普鲁士的哥尼斯堡城（哥尼斯堡城即现在俄罗斯境内的加里宁格勒）有一条贯穿全城的普雷格尔河，河中有两个岛屿，有七座桥将两岸与岛屿及岛屿之间连接，如图 6.24(a) 所示. 当时，当地人们热衷于一个难题：一个散步者怎样不重复地走完七桥，最后回到出发点. 这就是哥尼斯堡七桥问题. 试验者很多，但都没成功.
为了寻找答案，瑞士数学家昂哈德·欧拉（Leonhard Euler）对此问题进行研究，他将 4 块陆地抽象成 4 个顶点 A,B,C,D. 若两块陆地之间有桥，就在代表它们的顶点之间连边，如图 6.24(b) 所示. 哥尼斯堡七桥问题就是要寻找经过图中每条边一次且仅一次的简单回路. 欧拉在 1736 年的论文中指出，这样的回路是不存在的，从而得出哥尼斯堡七桥问题无解的结论. 这就是欧拉回路的来源.
定义 6.21 设 G=\langle V,E\rangle 是连通图（无向的或有向的）. G 中经过每条边一次并且仅一次的通路称作欧拉通路；G 中经过每条边一次且仅一次的回路称作欧拉回路；具有欧拉回路的图称为欧拉图.
注意，只有欧拉通路无欧拉回路的图不是欧拉图. 在图 6.25 中，图(a)，(d) 都既无欧拉回路，也无欧拉通路. 图(b)，(e) 均只有欧拉通路，但无欧拉回路. 所以，图(a)，(b)，(d)，(e) 4 个图都不是欧拉图. 而图(c)，(f) 中均存在欧拉回路，所以它们都是欧拉图. 其中一个是无向欧拉图，一个是有向欧拉图.
下面给出存在欧拉回路和欧拉通路的充分必要条件.
定理 6.10 无向图 G 有欧拉回路，当且仅当 G 是连通图且无奇度顶点.
G 有欧拉通路但无欧拉回路，当且仅当 G 是连通图且恰好有两个奇度顶点. 在恰好有两个奇度顶点的连通图中，每条欧拉通路都以这两个奇度顶点为端点.
证明从略.
图 6.24(b) 中的 4 个顶点都是奇度的，根据这个定理，它没有欧拉回路，甚至也没有欧拉通路，因此哥尼斯堡七桥问题无解.
例 6.13 判断图 6.26 给出的多个图中，哪些图中有欧拉通路，但无欧拉回路？哪些图是欧拉图？
解 图 6.26(d) 和 (e) 两个图均各有两个奇度顶点，因而它们都存在欧拉通路，但无欧拉回路. 图 6.26(a) 和 (f) 两图中的奇度顶点个数分别为 8 和 4，因而不可能存在欧拉通路、更无欧拉回路. 图 6.26(b) 和 (c) 两图中均无奇度顶点，因而都存在欧拉回路，即它们都是欧拉图.
对于连通的有向图是否有欧拉通路或回路由下面定理给出判断.
定理 6.11 有向图 D 有欧拉回路，当且仅当 D 是连通的且所有顶点的入度等于出度.
有向图 D 有欧拉通路但无欧拉回路，当且仅当 D 是连通的，且除了两个例外的顶点外，其余顶点的入度均等于出度，这两个例外的顶点中，一个顶点的入度比出度大 1，另一个顶点的入度比出度小 1.
例 6.14 在图 6.27 所示的多个图中，哪些有欧拉通路？哪些是欧拉图？
解 在图 6.27(a) 中所有顶点的入度等于出度，所以有欧拉回路，是欧拉图. 图 6.27(d)，(f) 中均有一个顶点的入度比出度大 1，还有一个顶点的出度比入度大 1，其余顶点的入度等于出度，所以有欧拉通路但无欧拉回路. 图 6.27(e) 为非连通图，因而不可能有欧拉通路，更无欧拉回路. 在图 6.27(b) 和 (c) 中，均存在入度比出度大 2，和出度比入度大 2 的顶点，因而它们都不可能存在欧拉通路，更无欧拉回路.
解读：欧拉问题问的是「边走一次」，所以判据只看度数：偶度进得来出得去，无奇度点就能闭合成回路，恰有两个奇度点就只能以它们为起点终点。七桥问题的本质是那 4 块陆地全是奇度顶点，连通却有 4 个奇点，故连通路都不存在。
6.4.3 哈密顿图
1859 年爱尔兰数学家威廉·哈密顿（William Hamilton）设计出一个在正十二面体上的游戏——周游世界问题. 他将 20 个顶点看作 20 个城市，每一条棱看作一条公路，要求从一个城市出发，沿着公路经过每一个城市一次且仅一次，最后回到出发的城市. 如果把正十二面体投影到平面上，如图 6.28 所示，就是要在图中找一条经过每一个顶点恰好一次的回路. 这就是哈密顿回路的来源.
定义 6.22 设 G=\langle V,E\rangle 为一图（无向的或有向的）. G 中经过每个顶点一次且仅一次的通路称作哈密顿通路；G 中经过每个顶点一次且仅一次的回路称作哈密顿回路；若 G 中存在哈密顿回路，则称 G 为哈密顿图.
从定义不难看出以下 3 点：
（1）存在哈密顿通路（回路）的图一定是连通图；
（2）哈密顿通路是初级通路，哈密顿回路是初级回路；
（3）若 G 中存在哈密顿回路，则它一定存在哈密顿通路，但反之不真.
还应该指出，只有哈密顿通路，无哈密顿回路的图不叫哈密顿图.
图 6.28 中 abcdefghijklmnopqrsta 是一条哈密顿回路. 在图 6.26 所示的 6 个无向图中，图(a) 只有哈密顿通路，无哈密顿回路，所以它不是哈密顿图. 其余各图中均有哈密顿回路（当然也有哈密顿通路），因而它们都是哈密顿图.
在图 6.27 所示的 6 个有向图中，除了图(e) 外，都有哈密顿通路. 其中图(b)，(c)，(f) 只有哈密顿通路，无哈密顿回路，所以它们都不是哈密顿图. 而图(a)，(d) 有哈密顿回路，所以它们都是哈密顿图.
与欧拉图的情况不同，直到目前，人们还没有找到哈密顿图的简单的充要条件，寻找这个条件是图论中的一个难题. 目前人们只找到一些判断存在性的充分条件和一些必要条件，下面介绍一个哈密顿图的必要条件.
定理 6.12 设无向图 G=\langle V,E\rangle 为哈密顿图，V_1 是 V 的任意真子集，则
其中，p(G-V_1) 为从 G 中删除 V_1 后所得图的连通分支数.
证明 因为 G 是哈密顿图，所以 G 中存在哈密顿回路. 设 C 为一条哈密顿回路，则 V_1 中的所有顶点在 C 上有些彼此相邻，有些不相邻.
于是
可是 C-V_1 是 G-V_1 的生成子图，因而 G-V_1 的连通分支数不会超过 C-V_1 的连通分支数，故
定理中给出的条件是必要的. 因而对一个图来说，如果不满足这个必要条件，它一定不是哈密顿图. 但是，满足这个条件的图不一定是哈密顿图.
推论 有割点的图一定不是哈密顿图.
证明 设 v 为图 G 的割点，则 p(G-v)\geqslant 2. 由定理 6.12 可知，G 不是哈密顿图.
例 6.15 证明图 6.29 中所示的 4 个图都不是哈密顿图.
解 在图 6.29(a) 中存在割点 u 和 v，所以图(a) 不会是哈密顿图. 在图(b) 中，令 V_1=\{a,b,c,d,e\}，从图中删除 V_1 得到 6 个连通分支. 而 |V_1|=5，由定理 6.12 可知图(b) 不是哈密顿图. 在图(c) 中，令 V'=\{a,b,c\}，删除 V' 得到 4 个连通分支，所以图(c) 也不是哈密顿图（注意图 6.29(c) 中存在哈密顿通路，但不存在哈密顿回路）. 可以验证，图 6.29(d) 满足定理 6.12 中的条件，但它不是哈密顿图. 在图 6.29(d) 中，a，f，g 均为 2 度顶点，因而边 (a,b)，(a,c)，(d,f)，(f,c)，(e,g)，(g,c) 都应在 G 中任何哈密顿回路上. 但这是不可能的. 因为如若如此，c 在回路上要出现 3 次，这与哈密顿回路的定义相矛盾. 但图中存在哈密顿通路，如 abcgedf 就是图中的一条哈密顿通路.
下面给出一些充分条件，定理的证明都略去.
定理 6.13 设 G 是 n(n\geqslant 3) 阶无向简单图，若对于 G 中每一对不相邻的顶点 u,v，均有
则 G 中存在哈密顿通路. 又若
则 G 中存在哈密顿回路，即 G 为哈密顿图.
推论 设 G 是 n(n\geqslant 3) 阶无向简单图，若 \delta(G)\geqslant\frac{n}{2}，则 G 是哈密顿图.
由推论可知，对于完全图 K_n，当 n\geqslant 3 时为哈密顿图，完全二部图 K_{r,s} 当 r=s\geqslant 2 时为哈密顿图.
还必须指出，定理 6.13 给出的条件是哈密顿图的充分条件，但不是必要条件. 6 阶圈图 C_6 显然是哈密顿图，但 C_6 不满足定理 6.13 中的条件.
关于有向图中的哈密顿通路有下面定理.
定理 6.14 在 n(n\geqslant 2) 阶有向图 D=\langle V,E\rangle 中，如果略去所有有向边的方向，所得无向图中含生成子图 K_n，则 D 中存在哈密顿通路.
以上给出的定理和推论，要么是哈密顿图的必要条件，要么是充分条件，就是没有充分必要条件，这就给我们判断一个图是否为哈密顿图带来了很大不便. 证明一个图是哈密顿图最直接的方法是找到一条哈密顿回路，也可以通过证明它满足某个充分条件，如满足定理 6.13 或推论中的条件. 而证明一个图不是哈密顿图只能通过证明它破坏某个必要条件. 这些必要条件，除了定理 6.12 中给出的外，还有许多. 设 n 阶图 G 是哈密顿图，则 G 应满足以下诸条件：
（1）G 必须是连通图. 这是因为 G 中存在经过每个顶点的圈，故 G 是连通的.
（2）G 中的边数 m 必须大于等于顶点数 n. G 中任何一条哈密顿回路中都具有 n 个顶点，n 条边，所以 G 中边数不能小于顶点数.
（3）若 G 中存在 2 度顶点 v，即 d(v)=2，则与 v 关联的两条边 e_i,e_j 必须在 G 中的任何哈密顿回路上.
（4）G 中必须在每条哈密顿回路中出现的边，不能构成边数小于 n 的初级回路（圈）. 若有这样的圈存在，它扩展不成 G 中的哈密顿回路，这与 G 是哈密顿图矛盾.
\cdots\cdots
若 G 破坏以上诸条件中的任何一条，它都不会是哈密顿图.
例 6.16 今有 a,b,c,d,e,f,g 7 个人，已知下列事实：
a 会讲英语；
b 会讲英语和汉语；
c 会讲英语、意大利语和俄语；
d 会讲日语和汉语；
e 会讲德语和意大利语；
f 会讲法语、日语和俄语；
g 会讲法语和德语.
问能否将这 7 个人安排就座圆桌旁，使得每个人都能与两边的人交谈？
解 做无向图 G=\langle V,E\rangle，V=\{a,b,c,d,e,f,g\}，E=\{(u,v)\mid u,v\in V\text{ 且 }u\neq v\text{ 且 }u\text{ 与 }v\text{ 会讲同一种语言}\}，如图 6.30 所示. 在图中，u 与 v 相邻当且仅当他们会讲同一种语言. 问题就变成了图中是否存在哈密顿回路（也即 G 为哈密顿图）. 不难看出 C=acegf dba 为 G 中的一条哈密顿回路，因而可以按 C 中顶点顺序安排座次，这样，相邻的两个人都会讲同一种语言，因而能交谈.
解读：欧拉看边、哈密顿看点，这一字之差导致难度天壤之别——「每边一次」有简洁的度数充要条件，「每点一次」至今只有零散的必要条件与充分条件。做题时方向也因此相反：证「是」靠构造回路或验证充分条件，证「不是」只能靠推翻某个必要条件（如定理 6.12）。
6.4.4 平面图
在图的理论探讨和实际应用中，平面图都具有重要意义. 本节将讨论平面图理论中的一些基本概念及平面图的判断. 在本节中专门讨论无向图，因而下面所谈图都是指无向图.
定义 6.23 图 G 如果能以这样的方式画在平面上：除顶点处处没有边交叉出现，则称 G 为平面图. 画出的没有边交叉出现的图称为 G 的平面嵌入或平面表示. 无平面嵌入的图称为非平面图.
在图 6.31 所示的图中，图(a) 为 K_4，图(b) 是它的平面嵌入，所以 K_4 是平面图. 单看图(b)，它当然也是平面图. 图(c) 是 K_5，无论怎样改变画法，边的交叉是不能全去掉的，图(d) 是 K_5 的边交叉最少的画法. 图(e) 是 K_{3,3}. 同 K_5 类似，无论怎么画，边的交叉是不能全去掉的，图(f) 是 K_{3,3} 的边的交叉最少的画法. 我们将证明，K_5，K_{3,3} 都不是平面图.
在讨论平面图的基本概念及性质时，所谈平面图，一般是指它的平面嵌入.
定义 6.24 设 G 是一个平面图，G 的边将所在平面划分成若干个区域，每个区域称为 G 的一个面. 其中面积无限的区域称为无限面或外部面，面积有限的区域称为内部面或有限面. 包围每个面的所有边构成的回路组称为该面的边界，边界的长度称为该面的次数. 面 R_i 的次数记作 \deg(R_i)，常将外部面记成 R_0.
在定义 6.24 中所指的回路可能是初级回路（圈），可能是简单回路，也可能是复杂回路. 特别地，非连通的平面图的外部面的边界是由几条回路组成的.
图 6.32(a) 是连通平面图，它有 4 个面，其中 R_1,R_2,R_3 是内部面，R_0 是外部面. R_1 的边界为 abda，\deg(R_1)=3. R_2 的边界为 bcdb，\deg(R_2)=3. R_3 的边界为 efge，\deg(R_3)=3. R_0 的边界为 dabcdefed，它是一个复杂回路，\deg(R_0)=9. 图 6.32(b) 是非连通的平面图. 它有 3 个面，\deg(R_1)=4，\deg(R_2)=3，R_0 的边界由 v_1v_2v_3v_4v_1 和 v_5v_6v_7v_8v_7v_5 两条回路组成，\deg(R_0)=9.
定理 6.15 在一个平面图 G 中，所有面的次数之和为边数的 2 倍，即
其中，r 为 G 的面数，m 为边数.
证明 对于 G 中的任意一条边 e，它或者是某两个面的公共边界，或者只出现在一个面的边界中. 当 e 是两个面的公共边界时，在每个面的边界上 e 都出现一次，因而对各面次数之和的贡献为 2. 当 e 只出现在一个面的边界中时，e 一定在这条边界上出现 2 次，因而对各面次数之和的贡献也为 2. 所以定理的结论成立.
关于平面图的平面嵌入，还应指出两点：
（1）同一个平面图 G 可以有不同形状的平面嵌入，但它们都是与 G 同构的；
（2）平面图 G 的外部面，可以通过改变顶点的位置由 G 的任何面充当.
图 6.33 中，图(b)，(c) 都是图(a) 的平面嵌入，它们的形状不同，但都与图(a) 同构. 图(b) 中的有限面 R_2'，在图(c) 中变成了无限面 R_0，R_0' 变成了图(c) 中的 R_2.
定义 6.25 设 G 为一个简单平面图. 如果在 G 的任意不相邻的顶点之间再加一条边，所得图为非平面图，则称 G 为极大平面图.
当 n\leqslant 4 时，K_n 都是极大平面图. K_5 删除任意一条边所得图也是极大平面图. 图 6.33 中所示的图不是极大平面图，在这个图中添加一条四边形的对角线后仍是平面图.
极大平面图有以下性质：
（1）极大平面图是连通的；
（2）n(n\geqslant 3) 阶平面图是极大平面图的充分必要条件是它的每个面的次数都为 3.
性质(1)的证明很简单. 设 G 是一个非连通的平面图，在它的两个连通分支的外部面的边界上各取一个顶点. 在这两个顶点之间添加一条边，仍为平面图，故 G 不是极大平面图.
性质(2)的证明略去. 利用性质(2)可以方便地判断一个平面图是否是极大平面图.
在图 6.34(a) 中各面均由三角形围成，它是极大平面图. 而图 6.34(b) 则不是极大平面图，它的外部面由 4 条边围成.
下面讨论连通平面图中顶点数，边数，面数之间的关系. 1750 年，数学家欧拉指出，任何一个凸多面体的顶点数 n，棱数 e 和面数 f 之间满足关系式：
可以把凸多面体投影到平面上成为一个连通的平面图，因而这个关系对连通的平面图也成立，这就是下述关于平面图的欧拉公式.
定理 6.16 设 G 为任意的连通的平面图，则
其中，n 为 G 的顶点数，m 为边数，r 为面数.
证明 对边数 m 作归纳法. 当 m=0 时，由 G 的连通性可知，G 必为孤立点，因而 n=1，r=1（即只有一个外部面），结论自然成立.
设 m-1(m\geqslant 1) 时结论成立，要证明 m 时结论也成立.
若 G 中有一个悬挂点 v，删除 v，得 G'=G-v，则 G' 是连通的，当然还是平面图. G' 中顶点数 n'=n-1，边数 m'=m-1，面数没变，即 r'=r. 由归纳假设应有
将 n'=n-1，m'=m-1，r'=r 代入上式，得
经过整理，得
若 G 中没有悬挂点，则必存在圈. 设 C 为一个圈，边 e 在 C 上. 令 G'=G-e，所得图 G' 仍连通，n'=n，m'=m-1，r'=r-1. 由归纳假设得
即
经过整理，得
得证 m 时结论也成立.
推论 G 是具有 k(k\geqslant 2) 个连通分支的平面图，则
其中，n,m,r 分别是 G 的阶数，边数和面数.
证明 设 G 的 k 个连通分支的顶点数、边数和面数分别为 n_i,m_i 和 r_i(1\leqslant i\leqslant k). 由欧拉公式，
求和得
显然，n=\sum\limits_{i=1}^{k}n_i，m=\sum\limits_{i=1}^{k}m_i. 又注意到每个分支有一个外部面，而 G 只有一个外部面，故 r=\sum\limits_{i=1}^{k}r_i-k+1. 代入上式，得到
例 6.17 设 G 是 n(n\geqslant 3) 阶 m 条边的简单平面图，证明：
（1）当 G 是极大平面图时，m=3n-6.
（2）当 G 不是极大平面图时，m<3n-6.
证明 只需证明(1). 由极大平面图的性质(2)，有
代入欧拉公式
整理得
定理 6.17 设 G 是连通的平面图，且每个面的次数至少为 l(l\geqslant 3)，则
其中，m 为 G 的边数，n 为顶点数.
证明 由定理 6.15 及本定理中的条件可知：
其中，r 为 G 的面数. 由于 G 是连通的平面图，因而满足欧拉公式，从中解出 r
将式(2)代入式(1)，经过整理，得
例 6.18 证明 K_5 和 K_{3,3} 都不是平面图.
证明 K_5 的顶点数 n=5，边数 m=10. 若 K_5 是平面图，则它的每个面的次数至少为 3. 由定理 6.15 得
这是个矛盾，因而 K_5 不是平面图.
K_{3,3} 有 6 个顶点，9 条边. 若 K_{3,3} 是平面图，它的每个面的次数至少为 4，由定理 6.15 得
这又是个矛盾，所以 K_{3,3} 也不是平面图.
K_5，K_{3,3} 是两个特殊的非平面图，在平面图的判断上起很重要的作用.
在讨论平面图的判断之前，先介绍消去 2 度顶点，插入 2 度顶点，同胚，初等收缩等概念.
在图 6.35(a) 中，从左到右的变换称为消去 2 度顶点 w. 图 6.35(b) 中从左到右的变换称为插入 2 度顶点 w.
定义 6.26 如果两个图 G_1,G_2 同构，或经过反复插入或消去 2 度顶点后同构，则称 G_1 与 G_2 同胚.
在图 6.36 中，图(b) 是经过图(a) 消去 2 度顶点 a,e，插入 2 度顶点 h,i 而得到的，图(a) 与图(b) 是同胚的.
定义 6.27 图中边 (u,v) 的收缩由下面方法给出：删除边 (u,v)，将 u 与 v 重合，所得顶点记为 u（或 v），使 u（或 v）关联除边 (u,v) 外，原来 u 与 v 关联的一切边.
在图 6.37 中，图(a) 中边 (v_2,v_3) 的收缩所得图由图(b) 中图给出.
1930 年，库拉图斯基（Kuratowski）给出了一个图是平面图的充分必要条件，这就是下面两个定理，称作库拉图斯基定理. 因为证明复杂，故省去证明.
定理 6.18 一个图是平面图当且仅当它不含与 K_5 同胚的子图，也不含与 K_{3,3} 同胚的子图.
定理 6.19 一个图是平面图当且仅当它没有可以收缩到 K_5 的子图，也没有可以收缩到 K_{3,3} 的子图.
例 6.19 证明图 6.38 中的 4 个图都是非平面图.
证明 在图 6.38(a) 中消去顶点 a,b,c,d,e，得到 K_5，故(a) 与 K_5 同胚. 由定理 6.18，它不是平面图. 也可以用定理 6.19 证明(a) 不是平面图，收缩边 (a,v_1)，(b,v_2)，(c,v_3)，(d,v_4)，(e,v_5)，得到 K_5.
图(b) 称为彼得松图，去掉两条虚线边得到的子图与 K_{3,3} 同胚，所以彼得松图不是平面图. 也可以用收缩边得到 K_5.
图(c) 去掉两条带双杠的边，得到 K_{3,3}，所以它不是平面图.
图(d) 去掉两条虚线边得到的子图与 K_5 同胚，所以它不是平面图. 另外，如果保留虚线边，去掉 4 条带双杠的边得到的图与 K_{3,3} 同胚.
例 6.20 画出所有非同构的 6 阶 11 条边的连通的简单非平面图.
解 若图 G 是非平面图，则它的母图也必然是非平面图. 已知 K_5 和 K_{3,3} 都是非平面图，因而将它们再增加若干个顶点和若干条边所得图仍然是非平面图. 根据题目要求，所要求的非平面图一定是由 K_5 增加一个顶点，增加一条边得到，或由 K_{3,3} 增加 2 条边所得到的图. 而由 K_5 增加一个顶点一条边所得的非同构的简单图只有两个，如图 6.39(a) 和 (b) 所示的图. 由 K_{3,3} 增加两条边得到的非同构的简单图也只有两个，如图 6.39(c) 和 (d) 所示的图.
定义 6.28 设平面图 G=\langle V,E\rangle，G 有 m 条边 e_1,e_2,\cdots,e_m，r 个面 R_1,R_2,\cdots,R_r. 用下述方法构造图 G^*：在 G 的每一个面 R_i 中任取一点 v_i^* 作为 G^* 的顶点. 记 V^*=\{v_1^*,v_2^*,\cdots,v_r^*\}. 对每一条边 e_k，若 e_k 是 R_i 和 R_j 的公共边界（i\neq j），则连接对应顶点 v_i^* 和 v_j^*，记 e_k^*=(v_i^*,v_j^*). e_k^* 与 e_k 相交. 若 e_k 只在 G 的一个面 R_i 的边界中出现，则以 R_i 中的顶点 v_i^* 为顶点做环 e_k^* 与 e_k 相交. 记 E^*=\{e_1^*,e_2^*,\cdots,e_m^*\}. 称 G^*=\langle V^*,E^*\rangle 为 G 的对偶图.
在图 6.40 中，由实心点和虚线边构成的图为由空心点和实线边构成的图的对偶图.
对偶图是相对于平面嵌入而言的. 同一平面图的不同平面嵌入（它们当然是同构的）的对偶图可能不同构. 例如，图 6.41(a) 和 (b) 中空心点和实线边构成的图是同一个平面图的两个平面嵌入. 它们的对偶图是实心点和虚线边构成的图. 这两个图不同构，一个的最大度数是 5，另一个最大度数是 4.
从对偶图的定义不难看出，G 的对偶图 G^* 是连通的平面图. G 与 G^* 的顶点数，边数与面数之间的关系由下面定理给出.
定理 6.20 设 G^* 是连通平面图 G 的对偶图，n^*,m^*,r^* 和 n,m,r 分别为 G^* 和 G 的顶点数，边数和面数，则
（1）n^*=r.
（2）m^*=m.
（3）r^*=n.
（4）设 G^* 的顶点 v_i^* 在 R_i 中，则
证明 由对偶图的定义可知，(1)，(2)，(4) 的成立是显然的. 下面证(3)成立.
由于 G 与 G^* 都是连通的平面图，因而顶点数，边数，面数之间都满足欧拉公式：
由式②得
将 n^*=r，m^*=m 代入式③，得
由式①知，
得证，
在定理 6.20 中，将 G 连通改为 G 具有 k(k\geqslant 2) 个连通分支的平面图，定理的结论中，(1)，(2)，(4) 均不变，只是(3) 中 r^*=n-k+1（请读者证明之）.
例 6.21 试证明：平面图 G 的对偶图 G^* 为欧拉图当且仅当 G 的每个面的次数均为偶数.
证明 先证必要性. 只需证，对于任意的 G 的面 R_i，\deg(R_i) 为偶数. 设 G^* 的顶点 v_i^* 位于 R_i 中，由定理 6.20 可知，\deg(R_i)=d(v_i^*)，由于 G^* 为欧拉图，所以 d(v_i^*) 为偶数，于是 \deg(R_i) 为偶数.
再证充分性. 只需证 G^* 连通并且无奇度顶点. 由平面图的对偶图都是连通的，再利用定理 6.20 可知，G^* 各顶点的度数均为偶数，所以 G^* 为欧拉图.
由例 6.21 不难看出，若 G 为二部图并且是平面图，则 G 的对偶图 G^* 均为欧拉图.
最后介绍图的着色问题和四色定理.
定义 6.29 设无向图 G 无环，对 G 的每个顶点涂一种颜色，使相邻的顶点涂不同的颜色，称为图 G 的一种点着色，简称着色. 若能用 k 种颜色给 G 的顶点着色，则称 G 是 k 可着色的.
图的着色问题就是要用尽可能少的颜色给图着色. 图 6.42 中给出各图的着色，不难验证所用的颜色数是最少的. 图 6.42(a) 和 (b) 是圈图，偶圈要用 2 种颜色，奇圈要用 3 种颜色. 图 6.42(c) 和 (d) 是轮图，奇阶轮图要用 3 种颜色，偶阶轮图要用 4 种颜色.
例 6.22 给出图 6.43 所示各图颜色尽可能少的着色.
解 图 6.43(a) 是二部图，可以用两种颜色着色，显然它也至少要用两种颜色，如图 6.44(a) 所示. 图 6.43(b) 是彼得松图，里面的 5 个顶点是一个圈，要用 3 种颜色. 给它们着色后，不难仍用这 3 种颜色给外面的 5 个顶点着色，如图 6.44(b) 所示. 对于图 6.43(c)，先用 3 种颜色给最外面的 3 个顶点着色，然后仍用这 3 种颜色给中层的 3 个顶点着色. 由于每个顶点都与最外面的 2 个顶点相邻，故着色的方法是唯一的. 最后，最里面的顶点由于与中层的 3 个顶点相邻，必须用第 4 种颜色着色，如图 6.44(c) 所示.
着色问题与哈密顿回路问题，至今没有找到有效的算法.
图着色问题有着广泛的应用. 当我们试图在有冲突的情况下分配资源时，就会自然地产生这个问题.
例 6.23 一个程序有 6 个变量 x_i，i=1,2,\cdots,6，其中，x_1 与 x_4,x_5；x_2 与 x_5,x_6；x_3 与 x_4,x_6；x_4 与 x_1,x_3,x_5,x_6；x_5 与 x_1,x_2,x_4,x_6；x_6 与 x_2,x_3,x_4,x_5 要同时使用. 计算机编译程序要给每一个变量分配一个寄存器. 为安全起见，要同时使用的两个变量不能分配同一个寄存器. 问编译这个程序至少要使用几个寄存器？如何分配？
解 做无向图 G=\langle V,E\rangle，其中 V=\{x_1,x_2,x_3,x_4,x_5,x_6\}，E=\{(x_i,x_j)\mid x_i\text{ 与 }x_j\text{ 要同时使用},i\neq j,i,j=1,2,\cdots,6\}，如图 6.45 所示.
不难看出给这个图着色至少需要 3 种颜色：x_4,x_5,x_6 分别着颜色 1,2,3，x_1 着颜色 3，x_2 着颜色 1，x_3 着颜色 2. 按照这种方式分配寄存器可以保证不会产生冲突，分配方案是：x_4,x_5,x_6 分别分配寄存器 1,2,3，x_1 分配寄存器 3，x_2 分配寄存器 1，x_3 分配寄存器 2.
在历史上，着色问题起源于地图着色. 19 世纪 50 年代一个青年学生注意到可以用 4 种颜色给英格兰的郡地图着色，使得相邻的郡着不同的颜色. 在这个基础上，他猜想任何地图都可以用 4 种颜色着色. 他的弟弟是德摩根的学生，他把哥哥的这个想法告诉了德摩根. 德摩根对这个问题非常感兴趣并把它公布于众. 这就是著名的四色猜想.
地图是连通无桥平面图的平面嵌入，每一个面是一个国家（或省、市、区等）. 若两个国家有公共的边界，则称这两个国家是相邻的. 对地图的每个国家涂上一种颜色，使相邻的国家涂不同的颜色，称为对地图的面着色，简称地图着色. 地图着色问题就是要用尽可能少的颜色给地图着色.
地图的面着色可以转化成平面图的点着色. 地图是无桥的平面图，它的对偶图无圈. 由于地图上的国家与它的对偶图的顶点一一对应，且两个国家相邻当且仅当对应的顶点相邻，因此，可以把地图的面着色转化成它的对偶图的点着色. 由于平面图的对偶图是平面图，从而地图着色（面着色）可以归结于平面图的点着色. 因此，四色猜想的提法后来变成：任何平面图都是 4-可着色的. 1890 年希伍德证明任何平面图都是 5-可着色的，称作五色定理. 此后一直没有什么进展，直到 1976 年两位美国数学家阿佩尔和黑肯终于证明了它，从而使得四色猜想成为四色定理. 阿佩尔和黑肯的证明是根据前人的证明思路，用计算机完成的. 他们证明，如果四色猜想不成立，则存在一个反例，这个反例大约有 2000 种（后来有人简化到 600 多种）可能，然后他们用计算机分析了所有这些可能，都没有导致反例，从而证明四色猜想成立. 但是，对四色定理的研究并没有到此结束，他们的证明毕竟是用计算机完成的. 寻找相对短的、能被人阅读和检查的证明，仍是数学家追求的目标.
定理 6.21（四色定理） 任何平面图都是 4-可着色的.
解读：平面图的全部数量关系都由欧拉公式 n-m+r=2 串起来：配合「每个面至少 3 条边」就得到 m\leqslant 3n-6，这正是判定 K_5、K_{3,3} 非平面图的杠杆；再配合库拉图斯基定理，就把「是不是平面图」归结为「有没有 K_5 或 K_{3,3} 的同胚/收缩子图」。对偶图则把「面」与「顶点」互换，因此「每面次数为偶数」与「对偶图是欧拉图」是同一件事的两面。