二分图、匹配、平面图与着色入门

上一章研究树时，我们一直在删边：只要把回路中的多余边拿掉，同时保持所有顶点连通，最后就会剩下一棵树。树回答的是“怎样用刚好够用的边维持连接”。这一章换一个角度，我们不再只问哪些点能连起来，而是开始处理边带来的限制：哪些对象只能跨组联系，哪些选择不能共用端点，哪些连线能在平面上避开交叉，哪些相邻对象不能拿到同一种资源。

这四个问题看着分散，其实都在做同一件事：先把现实约束翻译成图，再判断有没有同时满足全部约束的安排。二分图负责把对象分成两类，匹配从可行关系中挑出互不冲突的配对，平面图研究图能否无交叉地嵌入平面，着色则把冲突对象分到不同资源中。

这一章会把定义、判断方法和证明思路连成一条完整路线。读完以后，你不只应该记得几个结论，还应该能解释：为什么奇回路会破坏二分性，为什么 Hall 条件必须检查一整组对象，为什么平面图的每条边在面边界计数中恰好出现两次，以及为什么“找到一个三色方案”和“证明最少需要三色”是两回事。

学习目标

学完本章，你应该能够：

• 用二染色法判断有限无向图是否为二分图，并说明它与奇回路的关系。
• 区分匹配、极大匹配、最大匹配和完美匹配，使用增广路径改进已有匹配。
• 正确写出 Hall 条件，并从“瓶颈集合”理解它为什么是覆盖左部的匹配存在的充要条件。
• 区分普通完美匹配与带偏好次序的稳定匹配，知道两类问题的目标并不相同。
• 区分一幅有交叉的画法、平面嵌入和平面图，正确识别外面与桥在面边界中的作用。
• 在适用前提下使用欧拉公式和两个常见边数界，说明 $K_5$ 与 $K_{3,3}$ 为什么不是平面图。
• 用色数、团下界和最大度上界分析顶点着色，并把排课、频道分配和地图着色写成冲突图问题。
• 面对综合场景时，判断应当使用匹配、平面性还是着色，而不是只凭题目表面的词语套公式。

二分图：边只能在两类对象之间出现

先看一个任务分配场景。左边有若干学生，右边有若干项目；一条边表示“这名学生可以做这个项目”。学生之间不需要连边，项目之间也不需要连边，所有关系都从一类对象跨到另一类对象。这正是二分图最自然的样子。

设 $G=(V,E)$。如果可以把顶点集分成两个互不重叠的集合 $L$ 与 $R$，使每条边都有一个端点在 $L$、另一个端点在 $R$，那么 $G$ 是二分图。形式化地说，要求

并且对每条边 $\{u,v\}\in E$，$u$ 与 $v$ 分属两边。这里的 $(L,R)$ 叫作一个二分划分。

图画在纸面上的左右位置不重要。某个顶点即使被画在页面中央，只要所有顶点能够被分成满足条件的两组，这张图就是二分图。反过来，一张图画得很像左右两列，也不能替代对每条边的检查。

二染色法就是可执行的判定过程

判断一张小图能否二分，最实用的方法是尝试使用两种颜色染顶点，让每条边的两个端点颜色不同。这个过程可以按广度优先或深度优先搜索执行：

这个方法也解释了二分划分怎样得到：把蓝色顶点放入 $L$，把绿色顶点放入 $R$。如果某个连通分量没有边，那么它的孤立顶点放在哪一边都不会破坏条件。

为什么奇回路恰好是障碍

沿着一条路径走，每经过一条边，颜色就必须切换一次。走偶数步后颜色回到原色，走奇数步后颜色变成另一色。现在考虑一个长度为奇数的回路：从起点出发沿回路交替染色，最后一条边会要求起点既保持原色，又与自己已经染好的邻点异色，冲突无法消除。因此，只要图中有奇回路，它就不是二分图。

反方向稍微更有意思。假设一个连通图没有奇回路。选起点 $s$，把到 $s$ 的最短距离为偶数的顶点放入 $L$，距离为奇数的顶点放入 $R$。如果某条边 $uv$ 的两端距离奇偶性相同，那么从 $s$ 到 $u$、边 $uv$、再沿从 到 的路径返回，会产生一个奇数长度的闭合走法；删去其中成对绕行的部分后，会留下奇回路。这与“没有奇回路”矛盾。因此每条边都跨过 与 。

我们得到一个非常好用的判定结论：

一个有限无向图是二分图，当且仅当它不含奇数长度的回路。

这里也能接回上一章。树根本没有回路，所以当然没有奇回路；因此每棵树都是二分图。给树指定一个根以后，还可以直接按深度奇偶分组：偶数深度放一边，奇数深度放另一边。

完全二分图

如果左部有 $m$ 个顶点、右部有 $n$ 个顶点，而且每个左部顶点都与每个右部顶点相邻，这张图记作 $K_{m,n}$。它有

个顶点和

条边。后面研究平面图时，$K_{3,3}$ 会再次出现。它一方面是非常规整的二分图，另一方面却无法无交叉地画在平面上，这正好说明“二分”和“平面”是两种完全不同的性质。

匹配：从可行边中挑出互不抢占的安排

二分图只记录“谁可以选择什么”，还没有真的做分配。要把可行关系变成实际安排，我们需要从边集中选出一部分，并要求任何顶点都不被重复使用。

图 $G$ 中的一个匹配 $M$ 是一组边，其中任意两条边都没有公共端点。若顶点 $v$ 是某条匹配边的端点，就说 $v$ 被 $M$ 覆盖或匹配；否则它是未匹配顶点。匹配的大小是 $|M|$，也就是选中边的条数。

在人员—任务二分图里，这个定义刚好表示：每个人最多分到一个任务，每个任务最多交给一个人。注意“最多一个”并不保证所有人都有任务；匹配可以只覆盖一部分顶点。

四个容易混淆的词

• 匹配：任意两条选中边没有公共端点，不要求边数多。
• 极大匹配：已经无法再直接添加一条边而仍保持匹配。它是“加不动了”，却未必是全图最大的。
• 最大匹配：在所有匹配中，边数最多的匹配。
• 完美匹配：每个顶点都被覆盖的匹配。

极大和最大只差一个字，意思却差很多。比如路径 $v_1v_2v_3v_4$ 中，只选中间边 $v_2v_3$，已经没有边能直接加入，所以它是极大匹配；但选择 与 可以得到大小为 的匹配，因此原匹配不是最大匹配。

完美匹配关心覆盖范围。若二分图两边大小不同，覆盖所有顶点的完美匹配不可能存在，因为每条匹配边在两边各覆盖一个顶点。不过我们仍然可以问是否存在一个覆盖左部 $L$ 的匹配；这只要求每个左部顶点分到不同的右部对象，右部可以有剩余。

增广路径暴露了“怎么改”

从一个已有匹配 $M$ 出发，单纯盯着未选边很容易卡住：某个想要的任务已经被别人占用，似乎没有办法继续。真正有用的动作是允许沿一条路径重新安排。

一条相对于 $M$ 的交替路径，是指路径上的边依次在“不属于 $M$”与“属于 $M$”之间交替。若这条路径的两个端点都未被 $M$ 匹配，它叫作增广路径。它一定从未选边开始，也以未选边结束，所以未选边比已选边恰好多一条。

沿增广路径做“翻转”：原来选中的边取消，原来未选的边选中。内部顶点仍然恰好连接一条匹配边，而两个端点从未匹配变成已匹配，于是匹配大小增加 $1$。

假设当前匹配为

并且图中存在路径

其中 $C3$ 与 $B1$ 未选，$B3$ 已选。这条路径两端 $C$ 与任务 $1$ 都未匹配。翻转后得到

匹配大小从 $2$ 增加到 $3$。这个动作没有“抢走任务后不管原来的人”，而是把整条链一起调整。

更进一步，最大匹配与增广路径之间有一个重要判据：一个匹配是最大匹配，当且仅当不存在相对于它的增广路径。 “有增广路径就不是最大”已经由翻转直接说明；反方向可以比较当前匹配与一个更大匹配，把只属于其中一边的边分解成交替路径与交替回路。因为更大匹配多出边，总会出现一条两端未匹配的交替路径。

交互：检查端点是否被重复使用

下面的工具允许你点选人员与任务之间的边。先故意让两条边共享一个端点，观察冲突怎样出现；再清空选择，让工具自动找一组较大匹配。自动结果适合用来比较方案，但正文里的“最大”仍然要靠增广路径判据或完整算法确认，不能只凭按钮名称判断。

例题：把限制最紧的对象先安置

有四名助教 $A,B,C,D$ 和四项任务 $1,2,3,4$，可行关系为：

• $A$ 能做 $1$ 或 $2$；
• $B$ 只能做 $2$；
• $C$ 能做 $2$ 或 $3$；

问是否存在完美匹配。

这道题可以靠“先处理最紧的对象”快速完成，但这个经验不是存在性定理。复杂图里，即使每个人至少有两个选择，也可能有一整组人挤在同一小批任务上。要准确识别这种集体瓶颈，需要 Hall 条件。

Hall 条件：不要只检查一个人，要检查一整组人

设 $G$ 是二分图，左右两部为 $L$ 与 $R$。对任意 $S\subseteq L$，记 $N(S)$ 为 $S$ 中所有顶点在右部的邻居集合：

如果希望找到一个覆盖整个左部 $L$ 的匹配，那么任意一组左部顶点 $S$ 合起来都必须至少拥有 $|S|$ 个可选邻居：

这就是 Hall 条件。违反它的集合 $S$ 可以叫作瓶颈集合。

必要性为什么几乎不用算

假设已经有一个覆盖 $L$ 的匹配。取任意 $S\subseteq L$，其中每个顶点都匹配到了一个右部邻居；不同左部顶点匹配到的右部顶点必须不同。于是 $S$ 的 $|S|$ 个顶点至少需要 $|S|$ 个不同邻居，所以

若三名申请者合起来只连接到两个岗位，不管怎样安排，两个岗位最多覆盖两人，第三个人一定落空。这其实就是鸽巢原理在匹配问题中的样子。

充分性真正强在哪里

Hall 条件不只是一条排除规则。它的强结论是：如果左部的每个子集都没有瓶颈，那么一定存在覆盖整个左部的匹配。

证明的核心可以用左部顶点数做强归纳。我们不把细节藏在“显然可以继续”里，而是看清楚为什么只有两种情况。

这段证明解释了 Hall 条件的结构：有余量时可以先做一个局部选择；没有余量时，就把恰好卡满的部分整体切出来先解决。两种情况都能把问题缩小，而不会丢掉存在匹配所需的条件。

为什么实际检查不总是容易

如果左部有 $n$ 个顶点，就有 $2^n$ 个子集。Hall 条件虽然写得简洁，机械枚举全部子集却会很快变得昂贵。小题里通常先检查这些可疑位置：

• 邻居数特别少的单个顶点；
• 多个顶点共享同一小批邻居的区域；
• 题目中特别强调“只能选择”的对象；
• 全部左部顶点的邻居总数是否足够。

找到了瓶颈集合，就已经证明覆盖左部的匹配不存在；没有找到，只能说明暂时没发现反例，不能凭感觉宣布 Hall 条件成立。要证明存在，必须覆盖所有子集，或使用能够保证这一点的结构性论证与匹配算法。

稳定匹配是另一层要求

普通匹配只问边能否选得互不冲突。若每个参与者还给另一边排了偏好次序，就可能进一步要求稳定性：不能存在一对当前没有配在一起的对象，却都更喜欢彼此而不是自己的现有搭档。这样的一对通常叫阻塞对。

一个完美匹配可能不稳定。例如甲与岗位一、乙与岗位二都完成了配对，但甲更喜欢岗位二，岗位二也更偏好甲，那么这组安排覆盖了所有对象，却有一对双方都想离开现有安排的组合。

在两边人数相同、每个人都对另一边给出完整严格偏好次序的经典模型中，可以通过“尚未被拒绝的一方按偏好依次提出，接收方暂时保留当前最喜欢的提议并拒绝其余提议”的过程得到稳定匹配。这里我们只取一个建模提醒：

• 可行边与端点占用决定“是不是匹配”；
• 偏好次序与阻塞对决定“是不是稳定”。

这两个问题不能混写。Hall 条件处理可行关系下的覆盖，不读取偏好排名；稳定匹配过程处理偏好冲突，也不能替代一般二分图中的 Hall 检查。

平面图：当前有交叉，不等于永远无法消除交叉

从配对转向画图，我们先处理一个最常见的误判。把四个顶点画在正方形四角，再画两条对角线，图上出现交叉；这只能说明当前画法有交叉，不能说明这张图不是平面图。移动顶点、弯曲边，可能得到一幅没有交叉的新画法，而顶点与边的连接关系完全没变。

一幅图的画法把每个顶点放在平面上的不同位置，并把每条边画成连接对应端点的曲线。如果边只在它们原本共有的端点相交，没有自交，也没有在其他位置穿过顶点或边，这幅画法叫作平面嵌入。只要一张图存在至少一个平面嵌入，它就是平面图。

面包括最外面的无界区域

平面嵌入中的边把平面分成若干连通区域，这些区域叫作面。被边围住的区域容易看见，图外部向无限远延伸的无界区域也必须算一个面，通常叫外面。

面不是图在抽象意义下自带的第三类对象；它依赖具体嵌入。不过对连通平面图来说，不同平面嵌入虽然面形状可能不同，面数却会由顶点数与边数唯一确定，后面的欧拉公式会说明这一点。

面边界也不一定是简单回路。若一条边是桥，删除它会使图断开，那么在沿同一个面的边界行走时，会从桥的一侧走过去，又从另一侧走回来。因此桥在同一个面边界中出现两次。这个细节是边数界证明里“每条边总共被数两次”的一部分，不能因为图上看见一条线就只数一次。

树只有一个面

上一章的树连通且无回路。它的边无法围出任何内部区域，所以无论分支怎样弯曲，平面嵌入都只有外面这一个面。树满足 $E=V-1$，于是

这不是巧合。树会成为欧拉公式最自然的起点：先用生成树把所有顶点连起来，再把原图中其余边逐条加回去；每条不交叉的新边都会切开一个已有面。

欧拉公式：顶点、边和面怎样一起变化

设一个连通平面图已经给出一幅平面嵌入，记顶点数、边数、面数分别为 $V,E,F$。欧拉公式是

它的前提里有两个词必须同时看见：图要连通，而且 $F$ 是某个无交叉平面嵌入的面数，包含外面。若图还没有被证明是平面图，就不能先套公式“算出一个整数面数”，再反过来宣布它平面。

从生成树出发看证明思路

证明可以直接承接上一章的生成树。

另一种等价看法是从平面图中不断删除回路边。回路上的一条边不是桥，删掉它不会破坏连通性，却会把两个面合成一个面，于是 $E$ 与 $F$ 同时减少 $1$。最后剩下一棵生成树，表达式的值一路不变。

非连通图的版本

若平面图有 $c$ 个连通分量，平面上的外部区域会把各分量放在同一个共同的外面里。此时公式变为

本章后面的边数界证明会直接使用连通版本。遇到非连通图时，要么使用这个推广式，要么先说明如何在不产生交叉的情况下添加边，把各分量连接起来。

交互：让边数与面数一起变

下面的实验只展示连通平面图。切换预设图形后，先自己数内部面，再加上外面；接着添加一条不交叉边，观察 $E$ 与 $F$ 同时增加 $1$。删除操作只选择删除后仍保持连通的边，所以连通版欧拉公式始终适用。

例题：不要漏掉外面

一个连通平面图有 $8$ 个顶点和 $11$ 条边。求任意平面嵌入的面数。

平面图的边数界：从面边界反推边不能太多

欧拉公式把 $V,E,F$ 联系起来，但只靠它还不能排除某张图的平面性，因为 $F$ 仍然未知。下一步要利用面边界长度，把 $F$ 与 $E$ 再联系一次。

设 $G$ 是简单、连通的平面图，且 $V\ge 3$。在它的平面嵌入中，每个面边界的长度至少为 $3$。把所有面边界长度相加时，每条边总共贡献两次：非桥的两侧属于两个面，桥的两侧属于同一个面，但仍在该面边界中走过两次。因此

由欧拉公式 $F=2-V+E$，代入得到

整理后便是

这条不等式说的是：简单平面图的边数不会像完全图那样快速增长。平面空间能容纳的边有上限；顶点数固定时，边太多就一定出现无法消除的交叉。

没有三角形时界更强

如果图还是二分图，那么它没有奇回路，尤其没有三角形。平面嵌入中每个面边界的长度至少为 $4$，于是

仍代入 $F=2-V+E$：

整理得到

更一般地，只要简单连通平面图没有三角形，同样可以使用这个界；二分性是保证没有奇回路、从而保证面边界至少为 $4$ 的常见理由。

$K_5$ 为什么不是平面图

完全图 $K_5$ 有 $5$ 个顶点，每对顶点之间都有边，所以边数为

若它是简单连通平面图，就必须满足

但 $10>9$，矛盾。因此 $K_5$ 不是平面图。

$K_{3,3}$ 为什么需要更强的界

$K_{3,3}$ 有 $6$ 个顶点和 $3\cdot 3=9$ 条边。普通界只要求

并没有产生矛盾。这时必须使用它的二分性：二分图没有奇回路，每个面边界至少长 $4$，所以若它平面，就应满足

实际边数是 $9$，仍然多了一条，因此 $K_{3,3}$ 也不是平面图。

这两个例子展示了证明非平面性的典型路线：先假设存在平面嵌入，再使用所有这类嵌入都必须满足的边数界，最后由具体顶点数与边数制造矛盾。证明的力量来自“任何画法都必须满足界”，而不是尝试了几种画法都失败。

顶点着色：颜色其实是互不冲突的资源

现在把边的含义翻转一下。在匹配图里，边表示“可以配对”；在着色问题里，边通常表示“不能拿到相同资源”。课程之间有共同学生，就不能安排在同一考试时段；相邻地区共享一段边界，就不能涂成同色；覆盖范围重叠的发射台，就不能使用会相互干扰的同一频道。

图 $G$ 的一个合法顶点着色，是一个函数

满足对每条边 $\{u,v\}\in E(G)$ 都有

若存在至多使用 $k$ 种颜色的合法着色，就说 $G$ 是 $k$ 可着色的。能够完成合法着色的最小颜色数叫作图的色数，记为 $\chi(G)$。

颜色只是标签，不必真是红、黄、蓝。排课里的颜色是时段，寄存器分配里的颜色是寄存器编号，会议安排里的颜色可以是房间与时间的某种组合。建模时真正重要的是：一条边的两端为何不能获得同一个标签。

先分清上界与下界

如果你展示了一个使用 $4$ 种颜色的合法方案，只能推出

这是上界，因为它证明“至多需要四种”。要证明 $\chi(G)=4$，还需要一个下界，说明三种颜色无论如何都不够。

最常用的下界来自团。若图中有 $r$ 个顶点两两相邻，它们组成 $K_r$ 子图；这 $r$ 个顶点必须使用互不相同的颜色，所以

例如三角形的三个顶点两两相邻，至少需要三色；同时按顺序给它们三种颜色确实可行，所以三角形色数等于 $3$。

二分图就是可以二染色的图

如果图是二分图，把左部全部染成一种颜色、右部全部染成另一种颜色，就得到合法二染色。反过来，若图能用两种颜色合法着色，把两种颜色的顶点分别作为左右两部，每条边都会跨越两部，所以图是二分图。

因此，对至少含一条边的图，

没有边但有顶点的图只需一种颜色，所以这里特意加了“至少含一条边”的前提。

最大度给出一个容易证明的上界

记图的最大度为 $\Delta(G)$。任何有限简单图都满足

证明思路和前面删叶子的归纳很像。删去一个顶点 $v$，先给剩余图着色；把 $v$ 加回来时，它至多有 $\Delta(G)$ 个邻居，因此邻居至多占用 $\Delta(G)$ 种颜色。在准备好的 $\Delta(G)+1$ 种颜色中，至少有一种没有被邻居使用，可以分给 $v$。

这个界有时精确，例如完全图 $K_n$ 的最大度是 $n-1$，色数确实是 $n$；有时却很松。一个有许多叶子的星形图最大度很大，但中心一种颜色、所有叶子另一种颜色就够了，因为它是一棵树，也是二分图。

贪心着色为什么依赖顺序

贪心着色按某个顺序逐个处理顶点，每次给当前顶点使用“没有出现在已染色邻居中的最小颜色”。它一定能产生合法着色，也直接实现了 $\Delta(G)+1$ 的上界，但不保证用色最少。

原因并不神秘：算法只看已经处理的邻居，不会为了后面的顶点主动重排前面的选择。同一张图换一个顶点顺序，早期占用的颜色组合会不同，最终可能使用不同数量的颜色。

交互：把考试时段看成颜色

下面的工具中，每个顶点是一门课程，边表示两门课不能同一时段。先手动安排，观察同色冲突边怎样被标出；再运行贪心安排，并尝试改变课程的处理结果。工具显示的是一个合法上界，不自动证明所用时段数最少。

平面图与着色怎样接起来

地图着色是平面图与顶点着色相遇的地方。把每个区域变成一个顶点；若两个区域共享一段有正长度的边界，就连接对应顶点。只在一个角点接触的区域通常不算相邻。这样得到的邻接图可以画在平面上：把顶点放在区域内部，让边穿过共享边界连接相邻区域。因此地图着色变成了平面图的顶点着色。

四色定理说明每个平面图都可以用不超过四种颜色合法着色。这个结论很强，完整证明远超本章范围；我们把它作为已知事实使用，不假装用几幅图就证明了它。

不过，前面的边数界已经足以推到一个很有解释力的中间结论：按本章的简单图约定，每个平面图都有度数至多为 $5$ 的顶点。

为什么一定有一个低度顶点

假设某个简单连通平面图的每个顶点度数都至少为 $6$。由握手定理，所有顶点度数之和等于 $2E$，于是

从而 $E\ge 3V$。但平面图边数界给出

两者矛盾。因此至少有一个顶点的度数不超过 $5$。

这段证明把局部性质和整体计数连了起来：边数界限制平均度，平均度不可能达到 $6$，所以总能找到一个度数至多为 $5$ 的顶点。对非连通平面图，可以在某个有边的连通分量中应用同样思路；孤立顶点的度数本来就是 $0$。

五色定理的证明思路

度数至多为 $5$ 并不能直接用“删点再加回”证明五色，因为当这个顶点恰有五个邻居时，五种颜色可能都被邻居占用。还需要一步重新安排。

这给出五色定理：每个平面图都可以用至多五种颜色合法着色。四色定理把上界继续改进到四，但五色证明已经展示了本课程反复使用的套路：全局计数找到低度顶点，删点或收缩把图变小，再通过归纳把着色扩展回来。

综合建模：先判断边表示“允许”还是“冲突”

同一个现实场景常常会连续出现几种图。比如组织一场学生项目展：先要把学生分配到项目，再把有人员重叠的展示安排到不冲突的时段，最后还可能要把展位连接图画在一张平面导览图上。对象没有变，边的含义却在每一步改变。

模型选择对照

这一章的结论会在下一章的综合建模中被重新组合。到那时，题目不会主动告诉你“请用 Hall 定理”或“请画冲突图”；你需要先识别对象与关系，再决定证明的是存在性、不可能性、最优性，还是一个给定方案的正确性。

自测练习

练习一：二分性判定

一个图由一个四边形回路和一条连接到回路某顶点的树枝组成。它是否一定是二分图？

练习二：极大不等于最大

在路径 $v_1v_2v_3v_4$ 中，只选边 $v_2v_3$。它是极大匹配、最大匹配还是完美匹配？

练习三：寻找 Hall 瓶颈

左部为 $\{a,b,c,d\}$，右部为 $\{1,2,3,4\}$。其中 $a,b,c$ 都只连接到 $1,2$，而 连接到 。能否找到覆盖左部的匹配？

练习四：稳定与完美

一个匹配覆盖了偏好模型中的全部参与者。能否直接断定它是稳定匹配？

练习五：欧拉公式的前提

某图有 $V=6$、$E=9$。有人直接计算 $F=2-V+E=5$，并据此宣布这张图是平面图。这个推理错在哪里？

练习六：面数计算

一个连通平面图有 $10$ 个顶点、$15$ 条边。它的平面嵌入有多少个面？其中内部面有多少个？

练习七：选择正确边数界

一个简单连通二分平面图有 $V=8$ 个顶点。它最多可能有多少条边？

练习八：色数上下界

某图包含一个三角形，同时你找到了一个合法三色方案。它的色数是多少？

练习九：排课模型

五门课中，代数与物理冲突，物理与程序冲突，程序与文学冲突，文学与化学冲突，化学与代数冲突。至少需要几个时段？

知识路线回顾

这一章从上一章的树出发，先用深度奇偶把树看成二分图，再把二分图用于两类对象之间的分配。匹配要求选中边不共享端点；增广路径告诉我们怎样调整已有方案；Hall 条件则把“每个人都有选择”提升为“每一组人合起来都有足够多的选择”。

随后我们把注意力从端点占用转到平面嵌入。欧拉公式不是孤立的记忆式：树给出起点，加一条不交叉边会让边数与面数同时增加。继续对面边界计数，就得到 $E\le 3V-6$，在没有三角形时加强为 $E\le 2V-4$，从而排除 $K_5$ 与 的平面性。

最后，着色把边解释成冲突。一个可行着色给上界，团或奇回路给下界；二分性等价于二染色；平面图的边数界还保证存在低度顶点，并引出五色证明的删点、收缩与归纳思路。

真正需要带到综合建模中的，不是把这些结论分别背下来，而是形成一套提问顺序：顶点代表什么，边表示允许还是冲突，目标是覆盖、无交叉还是少用资源，当前结论证明的是“存在”“不可能”还是“最优”。当这些问题写清楚，后面的定理才会落在正确的位置上。

任务 $2$ 被占用后，$A$ 只能改选任务 $1$，所以边 $A1$ 也被迫进入匹配。