离散数学Ⅰ 笔记

前言

离散数学作为计软两院必修且较难的课程之一，历年以挂科率高、学习内容抽象、难度大而闻名。而且它本身作为一门专业课，可用的学习资源短缺，历年题几乎很少流出（只能靠有的老师在教学群中发真题，此行为取决于老师，有的会发，有的不会）。课本是吉大自研，与现行许多主流教材的定义、记法存在不少差异，几乎只能对照 PPT 或者老师讲课时理解学院“自成一派”的概念。

比较致命的是，历年的老题与现在考试的难度相去甚远，现行考试的整体难度要比所谓“学小帮”“吉井解学”之流所记载的历年题高出很多。这就导致许多同学对本门课的学习完全摸不着头脑，不知道真实考试时应该重点强化哪些知识，更何谈有效拔高。

因此，我把自己学习离散数学时留下的笔记、经验和资料重新整理在这里。它不是从零开始的完整教材，而是我在课程学习过程中的个人记录，主要用于梳理那些容易混淆或较难的概念。对我来说，比较合适的阅读顺序是：先完成每个小节的第一次学习并看过对应的 PPT，再回到这份笔记。 先掌握课程中的基本概念，再用这里的整理补充细节和理解疑难点。内容不求面面俱到，只保留我认为值得回看、能够帮助理清思路的部分。

集合论基础

集合的基本概念

集合论这部分（这里指不涉及第 1.2 节“关系”的纯集合论部分）期末考试基本不会单独设题，但是需要掌握证明两个集合之间包含关系和相等关系的几种方法，PPT 上都有写，此处不再赘述。这类证明思路最为基本，后面关系部分的大题也会用到。
总结一下课件和课后题中出现的集合性质。一些较基本或常用的性质不再赘述，例如由 $A\subseteq B$ 且 $B\subseteq C$ 可得 $A\subseteq C$；此处主要记载一些二级结论。

$$ \begin{aligned} A\subseteq B &\Longleftrightarrow \rho(A)\subseteq \rho(B),\\ A\subseteq C,\ B\subseteq C &\Longleftrightarrow A\cup B\subseteq C,\\ A\subseteq B &\Longrightarrow A\cap C\subseteq B\cap C,\\ A\cap C\subseteq B\cap C,\ A-C\subseteq B-C &\Longrightarrow A\subseteq B,\\ A\subseteq B &\Longrightarrow A\cup C\subseteq B\cup C,\\ A\subseteq C,\ B\subseteq D &\Longrightarrow \rho(A\times B)\subseteq \rho(C\times D),\\ A\subseteq C,\ B\subseteq D &\Longrightarrow A\times B\subseteq C\times D,\\ B\subseteq C &\Longrightarrow A\times B\subseteq A\times C,\\ A\times B\subseteq A\times C,\ A\neq\varnothing &\Longrightarrow B\subseteq C,\\ \rho(A)\cup\rho(B) &\subseteq \rho(A\cup B),\\ \rho(A)\cup\rho(B)=\rho(A\cup B) &\Longleftrightarrow A\subseteq B\ \text{或}\ B\subseteq A,\\ \rho(A)\cap\rho(B) &=\rho(A\cap B),\\ \rho(A-B) &\subseteq \bigl(\rho(A)-\rho(B)\bigr)\cup\lbrace\varnothing\rbrace,\\ A-B=B-A &\Longrightarrow A=B. \end{aligned} $$

以上公式尤其注意哪些是单向推出，哪些是双向推出，哪些是包含于，哪些是相等。证明由于篇幅且期末重点不在此处便不再赘述，但是证明都不难，可以期末复习时用于练手。

关于环和（对称差）与环积这类较冷门的运算，最好在考前浏览一遍、留下印象。虽然历年真题尚未出现过这些运算，但作业题中出现过，因此仍需了解。

关系

关系实际上是一种特殊的集合，因此许多集合所具有的性质在关系中也有所体现。对于 PPT 中的关系图、关联矩阵、相邻矩阵（邻接矩阵）、关系的幂及其定理、五种关系性质（自反、反自反等）的关系图与关系矩阵表示，以及 PPT 上有关各种定理的证明（注意并非所有证明），都只需达到了解程度，不必深入掌握。另外，第二类 Stirling 数是软件学院后续选修课“组合数学”的内容，在本门离散数学课程中不作要求，也不必学习，浏览即可。
关系的各种定义比如关系的逆，关系的乘积，五种关系的性质这些需要牢记。关系的证明期末是有可能出大题，而关系的哈斯图和各种极大元极小元上下界之类期末必有一道大题（期末大题会比平常更综合，会综合比如第三章逻辑的内容一起考）。所以关于关系的证明以及哈斯图建议好好研究 PPT，争取顺利掌握，因为其实并不难。
对于关系的闭包，无需掌握其证明，只需知道闭包的定义以及三种闭包的表达式，期末可能会出一道小的简答题。
对于划分和加细这种概念，只需知道指的是什么意思即可，无需掌握相关证明。
PPT 上的“讨论以下几种关系的自反性、反自反性、对称性、反对称性和传递性”，以及“$R_1,R_2$ 为非空集合 $A$ 上的关系，如果它们满足某种性质，经过相应运算后得到的关系是否也满足同样的性质？”这两部分内容和表格，最好尽可能记住，简答题问到时可以节省时间、直接写出答案。对于后一个问题，此处再补充两个结论：

逆关系 $R^{-1}$： $R$ 具有的性质，$R^{-1}$ 也具有。即若 $R$ 具有自反性、反自反性、对称性、反对称性或传递性，则 $R^{-1}$ 具有相同性质。
关系的平方 $R^2$： 只有当 $R$ 具有自反性、对称性或传递性时，$R^2$ 才具有相同性质；其他性质一般不成立。

注意拟序关系，即具有反自反性和传递性的集合，是可以证明出来具有反对称性的，具体证明参考 PPT。
等价类的定义可以直接按如下形式理解：用 $[a]_R$ 表示元素 $a$ 的等价类，其中 $[a]_R=\lbrace x\mid x\in A\text{ 且 }xRa\rbrace$，$a$ 称为这个等价类的代表元。这个定义比前面对等价类的正式定义更直观：具有某种共同性质的若干元素可以归为一类，因而可以把它们放进同一个集合中，组成一个等价类。
由等价关系求商集比较简单。按照上面的理解，对任意 $a\in A$（注意是原始集合 $A$ 中的每个元素），判断它属于哪个等价类，从而划分出不同的等价类，最后把所有等价类放入一个大集合中，即得到商集。由划分求等价关系可使用公式：设 $C=\lbrace M_1,M_2,\ldots,M_n\rbrace$ 是集合 $A$ 的一个划分，则 $C$ 对应的等价关系为 $R=(M_1\times M_1)\cup(M_2\times M_2)\cup\cdots\cup(M_n\times M_n)$，其中 $\times$ 表示笛卡尔积，$M_1,M_2,\ldots,M_n$ 均为集合。因为商集本身就是集合 $A$ 的一个划分，所以也可以用该公式求出商集对应的等价关系。
Hasse 图中各个可比元素之间呈现出来的高低关系不必过于严格，大体能够看出即可。此外，根据 Hasse 图写偏序关系时，一定不要忘记体现自反性和传递性。例如，若 Hasse 图中有 $a-b-c$（符号“$-$”表示两个元素在 Hasse 图中相连），则写偏序关系时必须包含 $(a,a),(b,b),(c,c),(a,c)$。
注意：等价关系的定义要求集合 $A$ 非空，而偏序关系不要求集合 $A$ 非空。
对于偏序集 $(A,\leqslant)$ 的一个子集 $M$，有以下结论：

若 $M$ 的极大（小）元或最大（小）元存在，则它们必定属于 $M$。
若 $M$ 的最大（小）元存在，则该最大（小）元必为 $M$ 的上（下）确界。
若 $M$ 的上（下）界或上（下）确界存在，则它们必属于 $A$，但不一定属于 $M$。
若 $M$ 的某个上（下）界属于 $M$，则该上（下）界必为 $M$ 的最大（小）元。

最大元、最小元、上界、下界、上确界和下确界都是全局概念。也就是说，需要保证所取集合中的某个元素与集合中的任意元素都可比，才可能存在上述概念；否则不存在。
总结一下关系中的一些二级结论：

$\left(R\circ S\right)^{-1}=S^{-1}\circ R^{-1}$。
$\left(R\cup S\right)^{-1}=R^{-1}\cup S^{-1}$。
$\left(R\cap S\right)^{-1}=R^{-1}\cap S^{-1}$。
若集合 $A$ 上的关系 $R,S$ 都是对称的，则复合关系 $R\circ S$ 是对称的充要条件为 $R\circ S=S\circ R$。
若 $R$ 是自反的，则其对称闭包 $s(R)$ 和传递闭包 $t(R)$ 都是自反的。
若 $R$ 是对称的，则其自反闭包 $r(R)$ 和传递闭包 $t(R)$ 均是对称的。
若 $R$ 是传递的，则其自反闭包 $r(R)$ 也是传递的，而对称闭包 $s(R)$ 不一定传递。
若 $R\subseteq S$，则 $r(R)\subseteq r(S)$、$s(R)\subseteq s(S)$、$t(R)\subseteq t(S)$。
若 $(A,R)$ 是偏序集，且 $B\subseteq A$，则 $\left(B,R\cap(B\times B)\right)$ 也是偏序集。
当 $|A|=n$ 时，集合 $A$ 上共有 $n!$ 个全序关系。

映射

映射这节依旧基本上不可能考大题证明题，PPT 上的有关证明看看理解即可，不求深入掌握。只可能结合简答题中考一小问，基本上将映射这节相关概念掌握后再去弄会作业题中有关于映射部分的习题基本上就够用了。所以解忧给的历年真题中有关于可数无穷集以及不可数集合相关证明一律都不求深入掌握。
映射的定义需要重点掌握。注意 $\sigma(A)$ 与 $\sigma$ 的区别：前者是值域，后者本质上是一个关系。
注意，逆映射的定义中强调了，必须已经是双射的映射才存在逆映射。
关于可数无穷集以及不可数集合方面的证明题基本上都无需掌握，只需记住结论以及一些常见的可数无穷集和不可数集合即可。
有一种特殊的映射叫作恒等映射，这个映射课本中可能没有但是题中有，所以在此补充一下。

恒等映射：若对非空集合 $A$ 存在映射 $I:A\to A$，且对每个 $x\in A$ 都有 $I(x)=x$（即映射后的结果仍为自身），则称 $I$ 为集合 $A$ 上的恒等映射。例如，$\sigma^{-1}\circ\sigma$ 是一个恒等映射，因为 $\sigma^{-1}(\sigma(x))=x$。恒等映射必定是双射。

补充关于映射的二级结论。设 $\sigma:A\to B$、$\tau:B\to C$，则 $\tau\circ\sigma:A\to C$：
若 $\sigma$ 与 $\tau$ 均为单射或均为双射，则 $\tau\circ\sigma$ 一定分别是单射或双射。
若 $\tau\circ\sigma$ 是满射，则 $\sigma$ 不一定是满射，而 $\tau$ 一定是满射。
若 $\tau\circ\sigma$ 是单射，则 $\tau$ 不一定是单射，而 $\sigma$ 一定是单射。
若 $\tau\circ\sigma$ 是双射，则 $\sigma$ 一定是单射，$\tau$ 一定是满射。
对任意映射 $\sigma$ 以及集合 $A,B$，等式 $\sigma(A\cup B)=\sigma(A)\cup\sigma(B)$ 必定成立；关系 $\sigma(A\cap B)\subseteq\sigma(A)\cap\sigma(B)$ 总是成立，并且当 $\sigma$ 为单射时，其中的“$\subseteq$”可以改为“$=$”。
如果 $A,B$ 是可数无穷集合，那么 $|A|=|B|$ 不一定能推出 $A,B$ 之间一定存在双射，而存在双射才能推出 $|A|=|B|$。作业题中应该有相关例子，此处不再详细举反例。

古典数理逻辑

命题逻辑

本节出题点比较融合，在简答部分必有，在 Hasse 图部分有可能与之结合而进行考察，在最后大题部分必考一道形式演绎法。总之古典数理逻辑这一大章节中命题逻辑，谓词逻辑都属于本身不算不难，但是可能有一部分计算量的东西，务必牢固掌握。
若 $P,Q$ 是两个命题，则：

$$P\leftrightarrow Q=(P\to Q)\land(Q\to P).$$

关于完备集部分历年真题也基本上没有考过，考前系统复习的时候过一遍有个印象即可。
关于公式之间蕴涵的证明方法 PPT 上的务必掌握，本身并不难。
关于形式演绎法，只需记住 PPT 中标黄的基本蕴涵式，以及形式演绎法的三条规则（尤其是规则三）即可。这里补充几个小点：（1）看到 $P\to Q$，应立即想到它也能推出 $\neg Q\to\neg P$。后者是原命题的逆否命题；也可以把“$\to$”改写为析取形式，从而看出该结论。

（2）对于形式演绎法中的规则三，实际上在题目中是可以多次使用的，思维不要僵化，来看下面的题：

$$ \begin{aligned} &\text{用形式演绎法证明：}\quad \lbrace P \to R\rbrace \Rightarrow (Q \to R) \to ((P \vee Q) \to R) \\[8pt] &(1)\quad P \to R \qquad \text{规则 }1 \\[4pt] &(2)\quad Q \to R \qquad \text{规则 }3 \\[4pt] &(3)\quad P \vee Q \qquad \text{规则 }3 \\[4pt] &(4)\quad R \qquad \text{规则 }2,\ \text{根据 }(1),(2),(3) \\[4pt] &(5)\quad (P \vee Q) \to R \qquad \text{规则 }3,\ \text{根据 }(3),(4) \\[4pt] &(6)\quad (Q \to R) \to ((P \vee Q) \to R) \qquad \text{规则 }3,\ \text{根据 }(2),(5) \end{aligned} $$

注意到此题在（2）（3）两步连续用了两次规则三，于是能大大简化解题过程。所以需要注意规则三是可以多次使用的。

（3）对于形式演绎法过程中前后推得的逻辑结果，如果最后让你证明的是两个命题的合取式，那么可以直接对前面已经得到若干个结论之间合取从而推出最后的结果，来看下面的例子：

$$ \begin{aligned} &\text{ 试用形式演绎法证明 } \lbrace P \vee Q,\ Q \to R,\ P \to M,\ \neg M\rbrace \text{ 共同蕴涵 } R \wedge (P \vee Q). \\[8pt] &(1)\quad P \to M \qquad \text{规则 }1 \\[4pt] &(2)\quad \neg M \to \neg P \qquad \text{规则 }2,\ \text{根据 }(1) \\[4pt] &(3)\quad \neg M \qquad \text{规则 }1 \\[4pt] &(4)\quad \neg P \qquad \text{规则 }2,\ \text{根据 }(2),(3) \\[4pt] &(5)\quad P \vee Q \qquad \text{规则 }1 \\[4pt] &(6)\quad \neg P \to Q \qquad \text{规则 }2,\ \text{根据 }(5) \\[4pt] &(7)\quad Q \qquad \text{规则 }2,\ \text{根据 }(4),(6) \\[4pt] &(8)\quad Q \to R \qquad \text{规则 }1 \\[4pt] &(9)\quad R \qquad \text{规则 }2,\ \text{根据 }(7),(8) \\[4pt] &(10)\quad R \wedge (P \vee Q) \qquad \text{规则 }2,\ \text{根据 }(5),(9) \end{aligned} $$

注意，这道题要求证明的是 $R$ 与 $P\vee Q$ 的合取式，即 $R\land(P\vee Q)$。在推导过程中，如果先后得到了 $P\vee Q$ 和 $R$，如步骤（5）与（9）所示，最后就可以直接将二者合取得到结论。

单个文字既可以算作子句，也可以算作短语。连续析取或连续合取的式子，例如 $P\vee Q\vee R\vee\cdots$ 或 $P\land Q\land R\land\cdots$，既可以看作析取范式，也可以看作合取范式。
关于主析取范式，主合取范式这种其实就和大一上学期的数电中的最大项最小项本质是一样的，可以类比记忆复习，重点看看主析取范式和主合取范式之间的转换。

谓词逻辑

本节虽然是重点，期末必考前束范式、Skolem 范式，以及简答题中的小题或与 Hasse 图结合的题目，但本身难度并不高，认真学习 PPT 即可掌握。
关于自由变量和约束变量，除了在化前束范式时会用到改名规则，在化 Skolem 范式时也可能出现自由变量（某年计算机学院真题出现过）。此时如果询问 AI，它大概率会回答：“因为变量是自由变量，所以相当于该变量可以取任意值，需要在式子前加一个全称量词。”但是，据某位教授离散数学的计算机学院老师所说：如果化 Skolem 范式时存在自由变量，则不必处理自由变量，将其视为常量即可。因此，遇到这类问题时正常处理即可。考试以后大概率不会再出这种有争议的问题，留有印象即可。
下列两种写法都是正确的：

$\forall x\thinspace G(x)\land\forall x\thinspace H(x)=\forall x\bigl(G(x)\land H(x)\bigr)$；
$\forall x\thinspace G(x)\land\forall x\thinspace H(x)=\forall x\forall y\thinspace\bigl(G(x)\land H(y)\bigr)$。

前者使用了 PPT 中的引理 2，后者使用了改名规则。

汇总一下 PPT 中出现过的基本蕴涵式以及一些谓词公式，最好记下来，因为后面期末如果谓词公式和 Hasse 图结合起来考，你如果不知道这些结论的情况下需要自己一个一个去计算每对公式之间是否存在蕴涵关系之类的，很耗时间，所以最好记下来以快速写出答案节省时间给后面大题。

$$ \begin{aligned} &\text{当论域可数时有：}\quad \forall x \forall y\thinspace P(x,y) = \forall y \forall x\thinspace P(x,y), \quad \exists x \exists y\thinspace P(x,y) = \exists y \exists x\thinspace P(x,y) \\[8pt] &\text{}\\[4pt] &1)\quad \forall x\thinspace(A(x)\to B(x)) \Rightarrow \bigl(\forall x\thinspace A(x)\to \forall x\thinspace B(x)\bigr) \\[6pt] &2)\quad \bigl(\forall x\thinspace A(x)\vee \forall x\thinspace B(x)\bigr) \Rightarrow \forall x\thinspace\bigl(A(x)\vee B(x)\bigr) \\[6pt] &3)\quad \exists x\thinspace\bigl(A(x)\wedge B(x)\bigr) \Rightarrow \bigl(\exists x\thinspace A(x)\wedge \exists x\thinspace B(x)\bigr) \\[6pt] &4)\quad \bigl(\exists x\thinspace A(x)\to \forall x\thinspace B(x)\bigr) \Rightarrow \forall x\thinspace\bigl(A(x)\to B(x)\bigr) \\[6pt] &5)\quad \forall x\thinspace\bigl(A(x)\vee B(x)\bigr) \Rightarrow \bigl(\forall x\thinspace A(x)\vee \exists x\thinspace B(x)\bigr) \end{aligned} $$

在固定论域下，某个谓词公式所能蕴涵出的所有公式共有 $2^m$ 个（其中包含恒真公式）；这里的 $m$ 表示该谓词公式唯一等价的主合取范式所包含的极大项个数。这个结论来自作业题，对应证明可见课后题，此处不再展开。

图与网络

图

从图与网络这章开始，离散数学的难度开始陡然上升。图的重要性不言而喻，期末除了简答题之类的小腿，必有一道难度较高的证明题。如果想在期末尽力做出图论的证明题，必须在理解图的基本概念的基础上，加强训练，掌握一些基本的证明思路和方法，最后方可融汇贯通，在遇到新题型的时候不至于一点思路没有。
对于判断两个图是否同构，其实唯一标准的充要条件就是同构的定义：两个相邻的点映射到另一个图里面仍然相邻，其实就可以简单的理解为给原图的各个点重新命名后能得到一个新的图，并且点之间的相邻关系不发生改变。如果两个图之间同构，那么可以得到如下的必要条件：两个图的点数相同，边数相同，度序列相同（度序列就是你把这个图所有点的度数按照一定的顺序给列出来就叫度序列，一般按照的是单调递增（严格来说其实是非单调递减）的顺序把所有点的度数写出来，这叫不减度序列，后面第四节 Hamilton 中会详细学到），连通分支数相同。虽然说这些都是必要条件，即在满足这些条件的情况下，两个图是不一定同构的。但是如果出题出到了同构相关，一般它出的图都是可以直接通过上面的必要条件（尤其是度序列）直接判断出来两个图同不同构的（不同构肯定可以正确判断，因为度序列如果不同的两个图一定不同构，相当于原命题的逆否命题，但是如果要判断同构，严格来说不对，因为只是必要条件，但是鉴于出题不会出太特殊的情况，所以就做题这个角度而言可以暂时用这个技巧加快做题速度）。
关联矩阵和相邻矩阵（邻接矩阵）作为大题证明题出现的概率不大，所以只需要知道其概念会写对应的矩阵即可，无需掌握其相关的证明以及证明题。
关于 Dijkstra 算法考察概率较大，但是不一定每年都考。写这个算法主要是要将那个表格画出来，然后最后下结论，即某点到某点的最短路是什么，距离是多少。至于画完表格以后需不需要写过程，建议再详细问问老师，我个人觉得画表实际上就体现了算法的执行过程了，就不用再写多余的文字过程了。还有一点，课后题中有一个让你求任意两点之间的最短路那道题，如果要用 Dijkstra 一个一个求就太麻烦了，那道题实际上考察的是 Floyd 算法，可以求全源的最短路。所以那题不用在意，考试也不会考，因为本质不是 Dijkstra 算法适用的场合，考试肯定只会考你单个点到其他各点的距离，就该用 Dijkstra 了。）
$n$个顶点的简单图，当至少有$(n-1)(n-2)/2 +1$条边（实际上就是一个$n-1$个点的完全图多加一条边）的时候可以确保它一定是一个连通图。

树

树这部分其实期末历年以来最后的那一道证明题出现频率也算比较高的，主要就是需要记住树的那五个等价的条件（相关证明可以大概看看知道是什么思路即可，不用深入掌握），还有关于支撑树支撑子图的那个结论。Kruskal 算法特别简单，不再详说，按部就班来即可。还有课后章节测试第四章图部分的作业也有一些小题需要多看看，是关于树方面的结论或者证明。再强调一遍，如果 PPT 上有关于树方面的证明题还是必须掌握的，会有比较典型的思路。
一些 $n$ 阶完全图的非同构支撑子图和非同构支撑树数量总结如下（以下均为可能考查的内容）：

非同构支撑子图：$K_1$ 至 $K_5$ 的数量依次为 $1,2,4,11,34$。
非同构支撑树：$K_1$ 至 $K_7$ 的数量依次为 $1,1,1,2,3,6,11$。

如果单纯询问 $n$ 个顶点的图的支撑子图数量，则为 $2^{n(n-1)/2}$；支撑树总数为 $n^{n-2}$。

这部分内容其实我也觉得没有必要死记，奈何作业题中出现过，25 级考试也考过 $K_6$ 的非同构支撑树数量，所以当时稍作整理。本意应该是要求自己计数，但从应试角度看，记住答案可以节省不少时间。

有向图与 Euler 路

有向图这部分期末仍然在压轴题考相关的证明（如历年比较流行考的“竞赛图”，竞赛图貌似吉大离散课本中无此概念，但是在北大版本的离散教材中有此概念，如果考”竞赛图“它必定会在最后大题中给出你此图的定义后再让你做相关的证明，总之其实有点像新定义，但是方法还是基本的那些思路），有向图我更倾向于将其看作简单图的拓展，概念上的分类更细了，结论也更多。关于 Euler 图我基本上敢保证它期末不会考 Euler 图或者 Euler 相关的严格性的证明，因为涉及到 Euler 图相关的证明都是极难极难的，有可能老师都做不来，我个人是觉得涉及 Euler 图的严格证明远超课程要求，所以如果看课后题涉及到相关题目了解了解即可，不用深入掌握，如果真考基本上有可能全专业做不出来都是有可能的，相当于没有拉开差距，总之我个人的观点是不会考 Euler 图相关证明，也不会考 PPT 上定理的证明，只会考你 PPT 上的定理的应用，一般就在前面简答题考，就看你对定理记忆和应用的熟练度即可。
注意有限有向图的概念，要求的只是点集有限即可，边集可以无限。
注意：按照吉大 PPT 中的定义，有向回路必须是简单有向路，其长度可以为 $1$ 或 $2$，也就是说这里对长度没有额外限制。
注意有向图中如果仅仅只说“连通”指的是弱连通而非强连通。
如果看过别的学校的教材，你会发现别的教材对于欧拉路的定义可能与吉大 PPT 不同，但是肯定是需要以吉大 PPT 为准的。
关于 Euler 路与有向树的转换这部分内容，其实期末考的概率比较低，好像一般不爱考，但是如果追求离散得到好成绩的，我仍然建议掌握此内容。我翻译一下 PPT 中这两部分怎么转化的内容：

Euler 路转有向树：选取 Euler 路的起点（同时也是终点的那个点）作为有向树的根，然后对其他异于根的点发出的弧，只保留该点发出的所有弧中序号最大的那条弧即可，即其他每个点只保留一条出弧，保留原则是只保留序号最大的那条。

有向树转 Euler 路：先找图 $G$ 的一个支撑树 $G_0$，$G_0$ 就是要被转化的有向树；然后遍历 $G_0$ 中的所有弧，遍历弧的顺序所对应的路就是一条 Euler 路。遍历序列中第一条弧可以是 $G_0$ 中由根发出的任意一条弧。选定第一条弧后，对于其他非根结点，它们可能有多条入弧和出弧，具体走哪一条可以任意选择，但要确保它们直接指向根的弧最后经过。终止条件是 $G_0$ 中所有弧均已恰好经过一遍。

有向图有根，则其漠视图必定连通。有限有向图一定存在有向支撑树。具有 $n$ 个顶点的有向树有 $n-1$ 条弧（因为根据转化定理，它可以看作一棵树）。

Hamilton 图

关于 Hamilton 图这节我认为比较重要，因为这一部分既可以考小题简答题，也会考大题证明题。相比 Euler 图的证明难度稍微逊色但是也会有难题。此外就是关于 Hamilton 的各种充分条件和必要条件，如果让你判断一个图不是 Hamilton 图，首先想到关于连通分支的那个定理。此外就是闭合图是完全图的图是 Hamilton 图的这个定理用的比较多。总之就是能掌握的尽量掌握，确实是重点的一章。
习题 4.4-3 所证明的结论一定要记住，而且 PPT 中给出的证明较为简单，建议掌握。这样便相当于多了一个判定 Hamilton 路的充分条件。
注意：只有当图 $G$ 拥有 Hamilton 回路时，$G$ 才能称为 Hamilton 图；只有 Hamilton 路的图不是 Hamilton 图。
PPT 中的另一个结论：$n$ 个顶点的边数最多的非 Hamilton 图有 $\dfrac{1}{2}(n-1)(n-2)+1$ 条边，即图 $C_{1,n}$。这个结论较为重要，需要记住；证明并不复杂，PPT 和课后题中都有。
关于闭合图有如下结论：若一个图中任意两个不相邻的顶点 $u,v$ 均满足 $d(u)+d(v)\geq n$（其中 $n$ 为该图的顶点数），则该图的闭合图是完全图。条件中既可以写“任意不相邻两点”，也可以写“任意两点”。这是因为原图中相邻顶点之间已经有边，而不相邻的两点由于度数之和不小于 $n$，会在构造闭合图时被连接起来，因此所有顶点最终两两相邻，闭合图就是完全图。利用这一结论，可以重新表述第 4 点中的结论以及“闭合图为完全图则原图为 Hamilton 图”的充分条件。注意：上述结论只是“闭合图是完全图”的充分条件，而不是充要条件；考试中的大多数题目使用这一充分条件即可判断。

若一个具有 $n$ 个顶点（$n\geq3$）的图 $G$ 对任意两个不相邻的顶点 $u,v$ 都满足 $d(u)+d(v)\geq n-1$，则 $G$ 存在 Hamilton 路。

若一个具有 $n$ 个顶点（$n\geq3$）的图 $G$ 对任意两个不相邻的顶点 $u,v$ 都满足 $d(u)+d(v)\geq n$，则 $G$ 存在 Hamilton 回路，即 $G$ 是 Hamilton 图。注意，这一条件与“若图 $G$ 的闭合图是完全图，则 $G$ 是 Hamilton 图”并不等价，根本原因在于上面关于闭合图的结论只是充分条件，而不是充要条件。

对于 $C_{m,n}$ 这种图，PPT 中给出了其各顶点的不减度序列表达式，最好记住，考试时便不必现场画图，可以节省时间。
完全图 $K_n$ 中所有互异 Hamilton 回路的条数为 $\dfrac{(n-1)!}{2}$。这里“互异 Hamilton 回路”是指任意两条 Hamilton 回路只要有一条边不重合，就算互异。这个问题本质上是排列组合问题：Hamilton 回路是一个圈，把 $n$ 个顶点作环形排列，共有 $(n-1)!$ 种排列；但从同一顶点沿正、反两个方向绕同一个圈所得的 Hamilton 回路相同，因为它们的边集一致，所以还要除以 $2$，最终得到 $\dfrac{(n-1)!}{2}$。

图论证明题整理与总结

图论证明题一直是我在这门课中感到比较困难的部分，因此这里整理了一些证明思路和题型记录。内容可能覆盖考试范围之外，但对我来说，多看几种题型有助于积累方法，也方便之后回看和复盘。

我在《离散数学学习指导与习题解答》图论章节中标记的参考题：

例题中的 4.2.1—4.2.4 均可做；课后题部分（即 4.3 习题解答）中，4.3.1 除第 2 题外其余均可做；4.3.2 除第 2 题外，第 6、7、8、9、10 题均可做；4.3.3 中第 1、2、3、4 题可做，其他题不推荐，难度可能过大；4.3.4 除第 6 题外均可做。注意：4.3.4 第 3 题使用了下面将介绍的另一种重点方法，但这种做法比较复杂，推荐使用 PPT 中的加点法证明；书上的方法可作为拓展阅读。

方法整理

1. 极大路径法

极大路径法是一种证明回路、路径存在性等问题时常用的构造性方法。

基本思路如下：设 $G=(P,L)$ 是具有 $n$ 个顶点的图（注意：必须是有限图才能使用极大路径法），$t$ 是一条起点和终点都不与 $t$ 外顶点相邻的路径，则称 $t$ 为一条极大路径。也就是说，任取一条路径，如果它的起点或终点与路径外的某个顶点相邻，就把路径延长到该顶点；不断重复，直到不存在能与路径起点或终点相接的外部顶点，即路径无法继续延长时终止。此后可以利用极大路径的端点不与路径外顶点相邻这一性质，结合题目条件进行反证。

几点补充说明：（1）非完全的极大路径仅仅是不可继续延长的路径，不一定是整个图中的最长路径，否则就应称为“最长路径”而不是“极大路径”。（2）设极大路径为 $v_1v_2\cdots v_k$。由于 $v_k$ 必与 $v_{k-1}$ 相邻，且极大路径的端点没有路径外邻点，所以 $v_k$ 的所有邻点都位于该路径上，从而 $d(v_k)\leq k-1$。又因为 $d(v_k)\geq\min(G)$，所以 $\min(G)\leq d(v_k)\leq k-1$。由于 $k-1$ 正是该极大路径的长度，因此极大路径的长度不小于 $\min(G)$。（3）极大路径法不仅适用于简单图，也可以用于有向图。

简单图中的极大路径：设路径为 $L=v_0v_1\cdots v_k$。若端点 $v_0$ 和 $v_k$ 均没有不在路径 $L$ 上的邻点，则 $L$ 是简单图中的一条极大路径。若简单图有限，则这种路径显然存在。常见证明套路是：若题目条件能确定各顶点的度均大于 $1$，又因为与 $v_0$ 或 $v_k$ 相邻的所有顶点都在 $L$ 上，便可能由此构造回路、产生矛盾。

有向图中的极大路径：设有向路径 $L=v_0\to v_1\to\cdots\to v_k$。若既不能从 $v_k$ 出发沿弧的方向把路径延长到路径外的顶点，也不能在 $v_0$ 前面加入一个路径外顶点来延长路径，则称 $L$ 为极大有向路径。此时，如果 $v_k$ 仍至少有一条出弧，这条弧只能指向路径 $L$ 上的某个顶点，从而可以构造有向回路。

下面我们用极大路径法来实操几道题：

例题（1）

题目： 设 $G$ 是有限简单图，$|P(G)|=n$（$n\geq4$），且图 $G$ 的最小度满足 $\min(G)\geq3$。证明：图 $G$ 中存在长度不小于 $4$ 的回路。

证明： 若图 $G$ 只有一个连通分支，则直接对整个图进行下列分析；若有多个连通分支，则任取一个连通分支进行分析。设 $u,v$ 是该连通分支中的任意两个顶点。由于该分支有限且连通，$u,v$ 之间存在路径。不断延长该路径，直到路径的起点和终点都不与路径外的任何顶点相邻。记所得极大路径为 $v_0v_1\cdots v_k$。

由于 $\min(G)\geq3$，根据前面极大路径的性质，有 $k\geq\min(G)\geq3$。下面只考察端点 $v_0$。由于 $v_0$ 没有路径外邻点，所以它的所有邻点都位于该路径上。

若 $v_0$ 与 $v_k$ 相邻，则 $v_0v_1\cdots v_kv_0$ 构成一条长度至少为 $4$ 的回路，结论成立。若 $v_0$ 与 $v_k$ 不相邻，由 $d(v_0)\geq\min(G)\geq3$ 可知，除必与 $v_1$ 相邻外，$v_0$ 还至少与路径上的另外两个顶点 $v_m,v_n$ 相邻。不妨设 $1<m<n<k$，则 $v_0v_1\cdots v_n v_0$（或选取相应相邻点构造的子段）给出一条长度至少为 $4$ 的回路。

综上，无论 $v_0$ 是否与 $v_k$ 相邻，图 $G$ 中都存在长度至少为 $4$ 的回路。

通过这道题，我们能初步领略极大路径的使用方法，总体而言就是利用极大路径不与路径外的点相邻这个性质去根据题目条件灵活推导。

该结论还可以推广为：设 $G$ 是有限简单图，$|P(G)|=n$（$n\geq4$），且 $\min(G)\geq2$，则 $G$ 中存在长度至少为 $\min(G)+1$ 的回路。 证明与上面例题的思路相同，可以留作之后的练习。

例题（2）

题目： 设 $D=(V,A)$ 为有限有向简单图，记 $d^+(v)$ 和 $d^-(v)$ 分别为顶点 $v$ 的出度和入度，$\delta^+(D)=\min_{v\in V}d^+(v)$ 为最小出度，$\delta^-(D)=\min_{v\in V}d^-(v)$ 为最小入度。已知 $\delta^+(D)>0$、$\delta(D)\geq2$ 且 $\delta^-(D)>0$。证明：$D$ 中存在长度至少为 $\max\lbrace\delta^-(D),\delta^+(D)\rbrace+1$ 的有向回路。

这道题显然是将极大路径法推广至有向图的案例，注意仔细体会和理解下面的证明，其实你就能知道本质还是一样的，仍然是利用了极大路径没有路径外相邻的点这条最重要的前提。

在 $D$ 中取一条极大有向路 $L=v_1\to v_2\to\cdots\to v_k$。这里“极大”是指既不能在 $v_1$ 前面添加路径外的顶点，也不能在 $v_k$ 后面添加路径外的顶点。

先考察起点 $v_1$。因为 $\delta^-(D)>0$，所以 $d^-(v_1)\geq\delta^-(D)>0$，从而 $v_1$ 至少有一个入邻点。设 $x$ 是 $v_1$ 的任意入邻点，即存在弧 $x\to v_1$。若 $x\notin V(L)$，则可以得到更长的有向路 $x\to v_1\to v_2\to\cdots\to v_k$，这与 $L$ 是极大路径矛盾。因此，$v_1$ 的所有入邻点都在 $L$ 上。在 $v_1$ 的所有入邻点中，取下标最大的一个，记为 $v_i$，于是有弧 $v_i\to v_1$。由于 $D$ 是简单有向图，不存在反身弧，所以 $i\geq2$。此时 $v_1\to v_2\to\cdots\to v_i\to v_1$ 构成一个有向回路，记为 $C_1$，其长度为 $|C_1|=i$。因为 $v_i$ 是下标最大的、指向 $v_1$ 的顶点，所以 $v_1$ 的所有入邻点只能位于集合 $\lbrace v_2,v_3,\ldots,v_i\rbrace$ 中。该集合共有 $i-1$ 个顶点，因此 $d^-(v_1)\leq i-1$。另一方面，由最小入度的定义，有 $d^-(v_1)\geq\delta^-(D)$。于是 $\delta^-(D)\leq d^-(v_1)\leq i-1$，所以 $i\geq\delta^-(D)+1$。因此，$C_1$ 的长度满足 $|C_1|\geq\delta^-(D)+1$。

再考察终点 $v_k$。因为 $\delta^+(D)>0$，所以 $d^+(v_k)\geq\delta^+(D)>0$，从而 $v_k$ 至少有一个出邻点。设 $y$ 是 $v_k$ 的任意出邻点，即存在弧 $v_k\to y$。若 $y\notin V(L)$，则可以得到更长的有向路 $v_1\to v_2\to\cdots\to v_k\to y$，这同样与 $L$ 是极大路径矛盾。因此，$v_k$ 的所有出邻点都在 $L$ 上。在 $v_k$ 的所有出邻点中，取下标最小的一个，记为 $v_j$，于是有弧 $v_k\to v_j$。由于 $D$ 不含反身弧，所以 $j\leq k-1$。此时 $v_j\to v_{j+1}\to\cdots\to v_k\to v_j$ 构成一个有向回路，记为 $C_2$，其长度为 $|C_2|=k-j+1$。因为 $v_j$ 是下标最小的、被 $v_k$ 指向的顶点，所以 $v_k$ 的所有出邻点只能位于集合 $\lbrace v_j,v_{j+1},\ldots,v_{k-1}\rbrace$ 中。该集合共有 $k-j$ 个顶点，因此 $d^+(v_k)\leq k-j$。另一方面，由最小出度的定义，有 $d^+(v_k)\geq\delta^+(D)$。于是 $\delta^+(D)\leq d^+(v_k)\leq k-j$，所以 $k-j+1\geq\delta^+(D)+1$。因此，$C_2$ 的长度满足 $|C_2|\geq\delta^+(D)+1$。

最后，在 $C_1,C_2$ 中取长度较大的有向回路 $C$，则 $|C|\geq\max\lbrace|C_1|,|C_2|\rbrace\geq\max\lbrace\delta^-(D)+1,\delta^+(D)+1\rbrace=\max\lbrace\delta^-(D),\delta^+(D)\rbrace+1$。因此，$D$ 中必存在长度至少为 $\max\lbrace\delta^-(D),\delta^+(D)\rbrace+1$ 的有向回路。

例题（3）

题目： 证明：一棵恰有两个度为 $1$ 的顶点的有限树必是一条简单路。

这道题有两种证明思路：第一种是利用握手定理反证，证明除两个度为 $1$ 的端点外，其余顶点的度均为 $2$；第二种是使用极大路径法。下面采用第二种方法。

设 $u,v$ 是 $G$ 中两个度为 $1$ 的顶点。由 $G$ 的连通性，存在一条从 $u$ 到 $v$ 的简单路，记为 $L$。设该树的顶点集为 $P(G)$，欲证对任意 $w\in P(G)$，都有 $w\in V(L)$。反证：假设存在 $w_0\in P(G)$，但 $w_0\notin V(L)$。由树的连通性，必存在一条从 $u$ 到 $w_0$ 的简单路。由于 $u$ 的度为 $1$，$w_0$ 必经由某条路径连接到 $L$ 的内部顶点，而不是另行直接连接到 $u$。因为 $w_0$ 的度不小于 $2$，故存在顶点 $w_1$ 与 $w_0$ 相邻。设 $L^{\prime}$ 是从 $u$ 到 $w_0$ 的简单路。顶点 $w_1$ 不能位于 $L$ 或 $L^{\prime}$ 上，否则会构成回路。继续对 $w_1$ 作同样分析，可得到无限多个互不相同的顶点，与图的有限性矛盾。因此所有顶点都在 $L$ 上，故该树是一条简单路。

2. 最长路与最短路法

最长路、最短路法与极大路径法本质相近，只不过明确要求在所有路径中取最长或最短的一条。许多能用极大路径法解决的问题也能用最长路法处理，但有些能用最长路法处理的问题未必能用极大路径法解决。至于证明时应选最长路还是最短路，可以从二者的作用来理解：使用最长路，通常是为了给当前路径施加一个“下界”，然后通过构造更长路径产生矛盾；使用最短路，则通常是为了给当前路径施加一个“上界”，然后通过构造更短路径产生矛盾。具体选择要结合题目目标。

3. 反证法与数学归纳法

反证法不再赘述。数学归纳法主要有两种形式，且两者都曾在课后题中出现。

第一数学归纳法： 要证明命题 $P(n)$ 对所有 $n\geq n_0$ 成立，分两步：第一步，证明初始情形 $P(n_0)$ 成立；第二步，假设 $P(k)$ 成立，并在此假设下证明 $P(k+1)$ 成立，即证明 $P(k)\Rightarrow P(k+1)$。

第二数学归纳法（强归纳法）： 要证明命题 $P(n)$ 对所有 $n\geq n_0$ 成立，也分两步：第一步，证明初始情形 $P(n_0)$ 成立；第二步，假设 $P(n_0),P(n_0+1),\ldots,P(k)$ 全部成立，并在这些假设下证明 $P(k+1)$ 成立。

显然，我们常用的都是第一数学归纳法，对于第二数学归纳法用的很少，当然实战中也是可以用的。接下来我们用反证和数学归纳法的思路来看几道比较综合的题，注意这些题可能不仅仅涉及到反证和数学归纳的思路，也会包含前面讲过的最长路径，极大路径等等的思想，总之比较综合。

例题（1）

题目： 若 $G$ 是具有 $n$ 个顶点的连通简单图，且 $n\geq2z+1$、最小度 $\delta(G)=z$，证明：图 $G$ 中存在一条长度至少为 $2z$ 的简单路。（25 级计算机学院离散数学Ⅰ图论压轴证明题；最长路法与反证法）

设 $P$ 是图 $G$ 中的一条最长简单路，其顶点序列为 $P=v_0v_1v_2\cdots v_m$。这条路径包含 $m+1$ 个顶点，长度为 $m$。采用反证法，假设不存在题目所述的路径，即最长路 $P$ 的长度满足 $m<2z$。由于 $P$ 是最长路，路径端点 $v_0,v_m$ 不能与路径 $P$ 外的任何顶点相邻；否则可将该外部顶点加入 $P$，得到长度为 $m+1$ 的路径，与 $P$ 最长矛盾。因此，$v_0,v_m$ 的所有邻点都在 $P$ 上。由最小度 $\delta(G)=z$ 可知，$v_0$ 在集合 $\lbrace v_1,v_2,\ldots,v_m\rbrace$ 中至少有 $z$ 个邻点，$v_m$ 在集合 $\lbrace v_0,v_1,\ldots,v_{m-1}\rbrace$ 中也至少有 $z$ 个邻点。

定义两个下标集合：$S=\lbrace i\mid1\leq i\leq m,\ v_0\text{ 与 }v_i\text{ 相邻}\rbrace$，$T=\lbrace i\mid1\leq i\leq m,\ v_m\text{ 与 }v_{i-1}\text{ 相邻}\rbrace$。显然，$|S|=d(v_0)\geq z$，$|T|=d(v_m)\geq z$，且 $S,T\subseteq\lbrace1,2,\ldots,m\rbrace$。根据反证假设 $m<2z$，有 $|S|+|T|\geq2z>m$。由于集合 $\lbrace1,2,\ldots,m\rbrace$ 只有 $m$ 个元素，所以 $S\cap T\neq\varnothing$。因此存在下标 $j$（$1\leq j\leq m$），使得 $v_0$ 与 $v_j$ 相邻，且 $v_m$ 与 $v_{j-1}$ 相邻。利用这两条边，可以把原路径 $P$ 闭合为回路 $C=v_0v_1\cdots v_{j-1}v_mv_{m-1}\cdots v_jv_0$。该回路恰好包含路径 $P$ 上的全部 $m+1$ 个顶点。

此时使用图 $G$ 的连通性。若回路 $C$ 已包含 $G$ 的全部顶点，即 $m+1=n$，则 $m=n-1\geq2z$，与假设 $m<2z$ 矛盾。若 $C$ 未包含图中全部顶点，即 $m+1<n$，由于 $G$ 连通，必存在一个不在 $C$ 上的顶点 $u$，它与 $C$ 上的某个顶点 $v_k$ 相邻。于是可从 $u$ 出发，经 $v_k$ 后沿回路 $C$ 的一个方向遍历其余所有顶点，构造一条包含 $m+2$ 个顶点、长度为 $m+1$ 的简单路。这比最长路 $P$ 更长，同样产生矛盾。因此反证假设不成立，图 $G$ 中必存在长度至少为 $2z$ 的简单路。

例题（2）

题目： 设 $G$ 是具有 $n$ 个顶点、$m$ 条边的简单图，且 $m\geq n$。证明：$G$ 中必有回路。（可用归纳法或反证法）

最简单的证明是反设 $G$ 中无回路，再分连通与不连通两种情况。若 $G$ 连通，则 $G$ 是树，所以其边数为 $n-1<n$，与 $m\geq n$ 矛盾；若 $G$ 不连通，则每个连通分支都是树。设 $G$ 有 $k$ 个连通分支，则总边数为 $n-k<n$，仍与题设矛盾。因此 $G$ 必有回路。

下面给出一种类似归纳、也类似逐步加边的方法。设图 $G$ 的边为 $l_1,l_2,\ldots,l_m$，顶点为 $v_1,v_2,\ldots,v_n$，依次把边 $l_1,l_2,\ldots,l_m$ 加入仅含这 $n$ 个顶点的图中。加入某条边 $l_i$ 时，若出现回路，则命题得证；若始终未出现回路，那么当加入第 $n-1$ 条边后，所得图若连通便是一棵树，再加入任意一条边都会产生回路。由于 $m\geq n$，最终必有回路。

例题（3）

题目： 设 $T$ 是具有 $k+1$ 个顶点的树，其中 $k\geq1$。$G$ 是简单图，且最小度满足 $\delta(G)\geq k$。证明：$G$ 中存在与 $T$ 同构的子图。

证明： 对 $k$ 使用数学归纳法。

不妨设 $G$ 连通，否则可对 $G$ 的某个连通分支进行讨论。（1）当 $k=1$ 时，$T$ 为 $K_2$。由于 $\delta(G)\geq1$，图 $G$ 中至少有一条边。任取一条边 $e$，由 $e$ 及其两个端点构成的子图便与 $T$ 同构。

（2）假设当 $k=r$（$r\geq1$）时结论成立。下面证明当 $k=r+1$ 时结论仍成立。此时，$T$ 是具有 $r+2$ 个顶点的树。树 $T$ 至少有两个度为 $1$ 的顶点，任取其中一个记为 $v_0$，令 $T_1=T-\lbrace v_0\rbrace$，则 $T_1$ 是具有 $r+1$ 个顶点的树。由归纳假设，$G$ 中存在一个与 $T_1$ 同构的子图 $G_1$。

在 $T$ 中，设被删除的顶点 $v_0$ 与 $v_1$ 相邻，其中 $v_1\in V(T_1)$；设 $G_1$ 中与 $v_1$ 对应的顶点为 $u_1$。由于 $d_G(u_1)\geq r+1$，而 $G_1$ 只有 $r+1$ 个顶点，除 $u_1$ 外至多有 $r$ 个顶点，因此必存在顶点 $u_0\in V(G)\setminus V(G_1)$，使得 $u_0u_1\in E(G)$。令 $G^{\prime}=G_1\cup\lbrace u_0u_1\rbrace$，则 $G^{\prime}$ 与 $T$ 同构。由数学归纳法，结论成立。

例题（4）

题目： 设 $G$ 为连通简单图，$C$ 为 $G$ 中的一条回路。若从 $C$ 上删除任意一条边后，由 $C$ 中剩余边构成的路径都是 $G$ 中的最长路径，证明：$C$ 是 $G$ 中的 Hamilton 回路。

证明： 要证明 $C$ 是 Hamilton 回路，只需证明图 $G$ 的所有顶点都在 $C$ 上。

假设结论不成立，则存在一个顶点 $w\notin V(C)$。由于 $G$ 是连通图，所以能够找到 $C$ 上的一个顶点 $u$，以及一条连接 $w$ 与 $u$ 的路 $\Gamma=w\cdots u$，使得 $\Gamma$ 上的边都不在 $C$ 上，并且 $\Gamma$ 的长度至少为 $1$。设 $v$ 是 $C$ 上与 $u$ 相邻的一个顶点，即 $e=uv$ 是 $C$ 上的一条边。从圈 $C$ 中删去边 $e$，得到路径 $\Gamma_1=C-e=uv_1v_2\cdots v_rv$。再把路 $\Gamma=w\cdots u$ 接到 $\Gamma_1$ 的端点 $u$ 上，得到路径 $\Gamma_2=\Gamma_1\cup\Gamma=w\cdots uv_1v_2\cdots v_rv$。因为 $\Gamma$ 的长度至少为 $1$，所以 $\Gamma_2$ 比 $\Gamma_1$ 更长。但是，根据题设，从 $C$ 上删除任意一条边后得到的路径都是 $G$ 中的最长路径，因此 $\Gamma_1$ 应当是 $G$ 中的最长路径。这与 $\Gamma_2$ 比 $\Gamma_1$ 更长相矛盾。因此，不存在 $C$ 外的顶点，即 $G$ 中所有顶点都在 $C$ 上。所以 $C$ 是 $G$ 中的哈密顿回路。证毕。

例题（5）

题目： 设简单图 $G$ 有 $n$ 个顶点，边数为 $m$，且 $m>\binom{n-1}{2}$。证明：$G$ 是连通图。

证明： 使用反证法。假设 $G$ 不连通，则可把顶点集分成两个非空部分 $A,B$，其中 $|A|=k$、$|B|=n-k$，且 $1\leq k\leq n-1$，使得 $A,B$ 之间没有任何边。因此 $G$ 的边只能位于 $A$ 内部或 $B$ 内部，故

$$ m\leq\binom{k}{2}+\binom{n-k}{2} $$

固定 $n$，函数

$$ f(k)=\binom{k}{2}+\binom{n-k}{2} $$

在 $1\leq k\leq n-1$ 上的最大值于端点 $k=1$（或 $k=n-1$）处取得，此时

$$ f(1)=\binom{1}{2}+\binom{n-1}{2}=\binom{n-1}{2} $$

所以

$$ m\leq\binom{n-1}{2} $$

与题设 $m>\binom{n-1}{2}$ 矛盾。故 $G$ 连通。

例题（6）

题目： 证明：任何简单图都能把其所有顶点分成两组，使两端分别位于不同组中的边数不少于 $m/2$。

设图 $G$ 有 $m$ 条边。在所有把图中顶点分到两个组 $A,B$ 的分法中，选取一种分法，使得“一端在 $A$ 中、另一端在 $B$ 中”的边数最多。记在这种分法下，两端分别位于不同组中的边数为 $q$。任取一个顶点 $v$。记 $v$ 在自己所在组中的邻点数为 $s(v)$，在另一个组中的邻点数为 $t(v)$，则顶点 $v$ 的度满足 $d(v)=s(v)+t(v)$。

下面证明必有 $t(v)\geq s(v)$。假设 $t(v)<s(v)$，把顶点 $v$ 从当前所在的组单独移到另一个组。移动之前，连接 $v$ 与同组邻点的 $s(v)$ 条边的两个端点位于同一组中，而移动之后，这 $s(v)$ 条边的两个端点分别位于不同组中；移动之前，连接 $v$ 与另一组邻点的 $t(v)$ 条边的两个端点分别位于不同组中，而移动之后，这 $t(v)$ 条边的两个端点位于同一组中。因此，移动顶点 $v$ 后，两端分别位于不同组中的边数净增加 $s(v)-t(v)>0$，这与原来所选分法已经使这种边数最多相矛盾。故对每个顶点 $v$，都有 $t(v)\geq s(v)$。

由 $d(v)=s(v)+t(v)$ 以及 $t(v)\geq s(v)$，可得 $2t(v)\geq s(v)+t(v)=d(v)$，所以 $t(v)\geq \dfrac{d(v)}{2}$。对所有顶点的 $t(v)$ 求和。每一条两端分别位于不同组中的边，都会分别被它的两个端点计算一次，因此 $\sum\limits_{v\in V(G)}t(v)=2q$。另一方面，由握手定理可知 $\sum\limits_{v\in V(G)}d(v)=2m$，于是 $2q=\sum\limits_{v\in V(G)}t(v)\geq \dfrac{1}{2}\sum\limits_{v\in V(G)}d(v)=\dfrac{1}{2}\cdot 2m=m$，从而 $q\geq \dfrac{m}{2}$。因此，任何有 $m$ 条边的图都可以把顶点分成两个组，使得至少有 $\dfrac{m}{2}$ 条边的两个端点分别位于不同组中。

例题（7）

题目： 设 $G$ 是具有 $n$ 个顶点的简单图，$\delta$ 表示 $G$ 的最小度。证明：若 $\delta\geq\dfrac{n-1}{2}$，则 $G$ 连通。

证明： 使用反证法。假设 $G$ 不连通，则 $G$ 至少有两个连通分支。在所有连通分支中，取顶点数最少的一个，记为 $G_1$，并设 $G_1$ 有 $k$ 个顶点。由于 $G$ 至少有两个连通分支，且 $G_1$ 是顶点数最少的连通分支，所以 $k\leq\dfrac{n}{2}$。否则若 $k>\dfrac{n}{2}$，其他每个连通分支的顶点数也都不少于 $k$，仅取 $G_1$ 和另一个连通分支，它们的顶点总数便大于 $n$，与 $G$ 共有 $n$ 个顶点矛盾。任取 $v\in V(G_1)$。不同连通分支之间没有边，所以 $v$ 的全部邻点都只能位于 $G_1$ 中，因此 $d(v)\leq k-1\leq\dfrac{n}{2}-1=\dfrac{n-2}{2}<\dfrac{n-1}{2}$。又因为 $\delta$ 是 $G$ 的最小度，所以 $\delta\leq d(v)<\dfrac{n-1}{2}$，与题设 $\delta\geq\dfrac{n-1}{2}$ 矛盾。因此假设不成立，故 $G$ 连通。

4. 自补图

若一个图同构于它的补图，则称为自补图。自补图有两个重要性质：（1）一个图和它的补图合起来是一个完全图；（2）由于二者同构，可以使用前面介绍的同构必要条件，即点数相同、边数相同、度序列相同、连通分支数相同。

例题（1）

《离散数学学习指导与习题解答》中的例 4.2.7 是一道自补图题目，此处不再重复其证明。

例题（2）

题目： 若 $G$ 是具有 $n$ 个顶点的自补图，证明：$n\equiv0\pmod4$ 或 $n\equiv1\pmod4$。（25 级唐班计算机考试真题；“$\bmod$”表示同余，数论第三节会学习，可在学完对应内容后再看此题。）

证明： 设 $G$ 有 $m$ 条边。由于 $G$ 与其补图 $\overline{G}$ 同构，所以二者边数相等，$\overline{G}$ 也有 $m$ 条边。又因为 $G$ 与 $\overline{G}$ 的边合起来恰好构成完全图 $K_n$，所以 $2m=\dfrac{n(n-1)}{2}$，即 $m=\dfrac{n(n-1)}{4}$。边数 $m$ 必须是整数，因此 $4\mid n(n-1)$。由于 $n$ 与 $n-1$ 一奇一偶，必须有 $n\equiv0\pmod4$ 或 $n\equiv1\pmod4$。

5. 连通分支

处于同一连通分支内部的顶点必定彼此连通。

例题（1）

题目： 若简单图 $G$ 中恰有两个奇数度顶点，证明：这两个奇数度顶点必然连通。

证明： 使用反证法。假设这两个奇数度顶点不连通，则它们分别位于两个不同的连通分支中。由握手定理的推论，每个图中的奇数度顶点个数均为偶数；而把这两个连通分支分别看作两个图时，它们各自都只有一个奇数度顶点，与握手定理的推论矛盾。因此，这两个奇数度顶点必然连通。

6. 删点、删边、删圈与加点、加边、加圈归纳法

除了极大路径法所代表的一类“加”的做法外，还有一类“删”的方法。这类方法常用于树的相关题型，一般在删除某些结构后配合数学归纳法。

例题（1）

题目： 设 $G$ 是一个不含回路的简单图，且 $G$ 有唯一的一棵支撑树 $T$。证明：$G=T$。

因为 $T$ 是 $G$ 的支撑树，所以两图的点集满足 $V(T)=V(G)$，并且边集满足 $E(T)\subseteq E(G)$。

下面证明 $E(G)\subseteq E(T)$。任取一条边 $l\in E(G)$，反设 $l\notin E(T)$。设 $l=uv$，由于 $T$ 是树，所以在 $T$ 中存在唯一一条连接 $u$ 与 $v$ 的路径。将边 $l$ 加入 $T$ 后，这条路径与边 $l$ 共同构成唯一的回路。从该回路中删除一条不同于 $l$ 的边 $e$，得到图 $T^{\prime}=T+l-e$。删除 $e$ 后回路被破坏，因此 $T^{\prime}$ 不含回路；同时，由于 $e$ 位于回路上，删除 $e$ 后，原来由 $e$ 连接的两个顶点仍可沿回路中的其余边相互到达，所以 $T^{\prime}$ 仍然连通。此外，$T^{\prime}$ 包含 $G$ 的全部顶点。因此，$T^{\prime}$ 也是 $G$ 的一棵支撑树。又因为 $l\in E(T^{\prime})$ 而 $l\notin E(T)$，所以 $T^{\prime}\ne T$。这与 $G$ 只有唯一一棵支撑树 $T$ 矛盾。

故任意 $l\in E(G)$ 都有 $l\in E(T)$，即 $E(G)\subseteq E(T)$。结合 $E(T)\subseteq E(G)$ 以及 $V(T)=V(G)$，可得 $G=T$。

例题（2）

题目： 设 $G$ 是有限连通图，$l$ 是 $G$ 中任意一条边。证明：$G$ 中存在一棵包含边 $l$ 的支撑树。

因为 $G$ 是有限连通图，所以 $G$ 至少存在一棵支撑树。任取 $G$ 的一棵支撑树 $T$。

若 $l\in E(T)$，则 $T$ 本身就是一棵包含边 $l$ 的支撑树，结论成立。

下面考虑 $l\notin E(T)$ 的情况。设 $l=uv$。因为 $T$ 是树，所以在 $T$ 中存在唯一一条连接 $u,v$ 的路径。将边 $l$ 加入 $T$ 后，边 $l$ 与这条路径共同构成唯一回路 $C$，且 $l\in E(C)$。在回路 $C$ 中任取一条不同于 $l$ 的边 $e$，令 $T^{\prime}=T+l-e$。由于从回路中删除了一条边，所以 $T^{\prime}$ 不含回路；又因为 $e$ 位于回路上，删除 $e$ 后，其两个端点仍然可以通过回路中剩余的边相互到达，所以 $T^{\prime}$ 仍然连通。在此过程中没有删除任何顶点，因此 $V(T^{\prime})=V(G)$。

所以 $T^{\prime}$ 是 $G$ 的一棵支撑树。由于删除的边 $e\ne l$，故 $l\in E(T^{\prime})$。因此，$G$ 中存在一棵包含指定边 $l$ 的支撑树。

例题（3）

题目： 若 $r$ 是有向图 $G$ 的根，证明：$G$ 必含有一棵以 $r$ 为根的有向支撑树。

设 $G$ 有 $n$ 个顶点。我们从顶点 $r$ 开始，逐步构造一个以 $r$ 为根、所有弧都朝向根的有向树。

首先令 $T_1$ 只含有顶点 $r$，即 $V(T_1)=\lbrace r\rbrace$，$E(T_1)=\varnothing$。显然，$T_1$ 是一棵以 $r$ 为根的有向树。假设经过若干次扩充，已经构造出一棵以 $r$ 为根的有向树 $T_k$，其中 $1\le k<n$，并且 $T_k$ 恰好有 $k$ 个顶点。因为 $k<n$，所以 $V(T_k)\ne V(G)$，从而 $G$ 中至少存在一个不属于 $T_k$ 的顶点。任取一个顶点 $x\in V(G)\setminus V(T_k)$。由于 $r$ 是 $G$ 的根，所以在 $G$ 中存在一条从 $x$ 到 $r$ 的有向路，记为 $x=x_0\to x_1\to\cdots\to x_m=r$。在这条有向路上，起点 $x_0=x$ 不属于 $V(T_k)$，而终点 $x_m=r$ 属于 $V(T_k)$。因此，沿着这条有向路从 $x$ 向 $r$ 行进时，必然会第一次进入 $T_k$。设 $x_j$ 是这条有向路上第一个属于 $V(T_k)$ 的顶点。因为 $x_0\notin V(T_k)$，所以 $j\ge1$。由 $x_j$ 的选取可知，$x_{j-1}\notin V(T_k)$，并且由于 $x_0\to x_1\to\cdots\to x_m$ 是一条有向路，故 $x_{j-1}x_j\in E(G)$，方向为 $x_{j-1}\to x_j$。现在把新顶点 $x_{j-1}$ 以及弧 $x_{j-1}\to x_j$ 加入 $T_k$，定义 $T_{k+1}$ 为 $V(T_{k+1})=V(T_k)\cup\lbrace x_{j-1}\rbrace$，$E(T_{k+1})=E(T_k)\cup\lbrace x_{j-1}\to x_j\rbrace$。

下面说明 $T_{k+1}$ 仍然是一棵以 $r$ 为根的有向树。

首先，$x_{j-1}$ 原来不在 $T_k$ 中，现在只通过一条弧 $x_{j-1}\to x_j$ 与 $T_k$ 连接。因此，在忽略弧的方向后，$T_{k+1}$ 是在树 $T_k$ 上增加一个新顶点，并用一条边把该新顶点与原树连接起来，所以 $T_{k+1}$ 仍然连通，并且不会产生回路。故 $T_{k+1}$ 的基础无向图仍然是一棵树。其次，由于 $x_j\in V(T_k)$，而 $T_k$ 是以 $r$ 为根的有向树，所以在 $T_k$ 中存在一条从 $x_j$ 到 $r$ 的有向路。再在这条有向路前面接上弧 $x_{j-1}\to x_j$，便得到一条从新顶点 $x_{j-1}$ 到 $r$ 的有向路。原来 $T_k$ 中各顶点到 $r$ 的有向路没有受到破坏。因此，$T_{k+1}$ 中每个顶点都能沿有向路到达 $r$。所以，$T_{k+1}$ 是一棵含有 $k+1$ 个顶点、以 $r$ 为根的有向树。

按照上述方法，每次扩充恰好增加一个新顶点。由于 $G$ 只有 $n$ 个顶点，经过有限次扩充后，最终得到一棵有向树 $T_n$，满足 $V(T_n)=V(G)$。因此，$T_n$ 包含 $G$ 的全部顶点，并且是 $G$ 的子图，同时以 $r$ 为根，所以 $T_n$ 是 $G$ 中一棵以 $r$ 为根的有向支撑树。证毕。

例题（4）

题目： 设简单图 $G$ 有 $n$ 个顶点、$m$ 条边。证明：$G$ 的连通分支数满足 $c(G)\geq n-m$。（加边法）

证明： 从一个含有 $G$ 的 $n$ 个顶点但没有边的图出发，此时每个顶点自成一个连通分支，所以连通分支数为 $n$。现在把 $G$ 的 $m$ 条边逐条加入。每加入一条边 $e=uv$：若 $u,v$ 原来位于不同连通分支，则该边将两个分支合并，连通分支数减少 $1$；若 $u,v$ 已位于同一连通分支，则连通分支数不变。因此，每加入一条边，连通分支数至多减少 $1$。加入全部 $m$ 条边后得到图 $G$，连通分支数从 $n$ 至多减少 $m$，故 $c(G)\geq n-m$。

7. 竞赛图

把一个简单图的每条边都指定一个方向，所得有向图称为定向图；完全图的定向图称为竞赛图。竞赛图虽然未在吉大离散数学教材中专门讲授，但近两年计算机学院和软件学院都考过相关证明。考试通常会给出竞赛图的定义，解题时可以把它当作一般有向图处理。鉴于近两年均有考查，下面梳理竞赛图的基本性质和证明。其中例题（2）与例题（3）可在学有余力时阅读。

竞赛图的基本性质：

竞赛图是在完全图的基础上为每条边指定方向，因此任意两个顶点之间仍有且仅有一条有向边，不存在平行边或反身边。也就是说，竞赛图中不存在长度为 $1$ 或 $2$ 的有向回路。
竞赛图的边数等于对应完全图的边数。
每个顶点的总度仍为 $n-1$；指定方向后，应表述为每个顶点的入度与出度之和等于 $n-1$。

例题（1）

题目： 设 $G$ 是具有 $n$ 个顶点的竞赛图。证明：若 $G$ 中存在有向回路，则 $G$ 中必定包含一条长度为 $3$ 的有向回路。（25 级软件学院离散数学Ⅰ真题）

此题先看让你证明的是什么，一看是让你证明存在回路，那么我们应该立马想到极大路径/最长/最短路径的方法，这是证明有关于回路之类的很常用的手段。这是一个我们首先的思路。其次一般这些压轴题并不能只用单一方法证明，所以我们可以把极大路径/最长/最短路与两种最常用的证明手段反证/数学归纳结合起来，探索一下看看能不能做；

如果采用反证法并结合极大路径、最长路或最短路的思想，反证假设意味着竞赛图中的所有有向回路长度都不小于 $4$。接下来需要判断应使用哪一种路径方法。由于竞赛图中的有向回路长度本来就大于等于 $3$，此时若我们选用最短路的方法，相当于给要证明的回路施加了一个“小于等于3的上界”，因此我们能证明得到存在长度为3的有向回路（这个在前面第一次介绍最长/最短路的方法时候分析过了）因此，本题可以使用反证法与最短回路法证明。

证明（反证法与最短回路法）： 已知该 $n$ 阶竞赛图中存在有向回路。在所有有向回路中，选取一条长度最短的回路，记为 $C$，并设其长度为 $k$。反设图中不存在长度为 $3$ 的有向回路，则 $k>3$。将 $C$ 上的顶点按照有向边的连接顺序记为 $v_1,v_2,\ldots,v_k$，于是 $C=v_1\to v_2\to\cdots\to v_k\to v_1$。由于该图是竞赛图，任意两个顶点之间有且仅有一条有向边。考察 $v_1$ 与 $v_3$ 之间的有向边，只有以下两种情况：

情况一： 若有 $v_1\to v_3$，则可以绕过 $v_2$，得到有向回路 $v_1\to v_3\to v_4\to\cdots\to v_k\to v_1$。这条回路的长度为 $k-1$，与 $C$ 是最短回路矛盾。

情况二： 若有 $v_3\to v_1$，则 $v_1\to v_2\to v_3\to v_1$ 构成一条长度为 $3$ 的有向回路，与反证假设矛盾。

因此，只要 $k>3$，无论 $v_1$ 与 $v_3$ 之间的有向边方向如何，都会产生矛盾。故最短回路 $C$ 的长度只能为 $k=3$，从而图中必包含一条长度为 $3$ 的有向回路。

此外，本题还可以用第二数学归纳法进行证明。实际上，第二数学归纳法我个人认为其实可以优先考虑，因为它提供的前提直观上比第一数学归纳法更强，只是平常我们一般见到的都是第一数学归纳法，并且很多题第一数学归纳法足够了，也就没有这个意识。

第二数学归纳法证明：

当 $n=3$ 时，一个 $3$ 阶竞赛图若存在有向回路，该回路必然包含全部 $3$ 个顶点，它本身就是一条长度为 $3$ 的有向回路，命题成立。

假设对于所有满足 $3\leq m<n$ 的阶数 $m$（其中 $n\geq4$），任意 $m$ 阶竞赛图只要含有有向回路，就必然含有一条长度为 $3$ 的有向回路。

下面证明 $n$ 阶情形。考虑一个含有有向回路的 $n$ 阶竞赛图 $G$，设其中一条有向回路为 $C$，其长度为 $L$（$3\leq L\leq n$）。分两种情况讨论：

情况一：$L<n$。 由回路 $C$ 上的 $L$ 个顶点所导出的子图仍是一个竞赛图，并且含有有向回路。由于 $3\leq L<n$，根据归纳假设，这个 $L$ 阶子图中含有一条长度为 $3$ 的有向回路，因此原图 $G$ 中也含有这样的回路。

情况二：$L=n$。 此时 $C$ 经过图中全部顶点，设 $C=v_1\to v_2\to\cdots\to v_n\to v_1$。考察 $v_1$ 与 $v_3$ 之间的有向边。若 $v_3\to v_1$，则 $v_1\to v_2\to v_3\to v_1$ 是一条长度为 $3$ 的有向回路。若 $v_1\to v_3$，则可以跳过 $v_2$，得到长度为 $n-1$ 的有向回路 $v_1\to v_3\to v_4\to\cdots\to v_n\to v_1$。由这 $n-1$ 个顶点导出的子图是一个含有向回路的 $n-1$ 阶竞赛图。由于 $n-1\geq3$，根据归纳假设，它含有长度为 $3$ 的有向回路，因而原图 $G$ 中也含有这样的回路。

综上，任意含有有向回路的 $n$ 阶竞赛图都含有一条长度为 $3$ 的有向回路。由第二数学归纳法，命题对所有 $n\geq3$ 成立。

例题（2）

题目： 证明：每个竞赛图中都存在一个顶点 $v$，使得从 $v$ 到其余任意顶点都有一条长度至多为 $2$ 的有向路。（最大出度法；该方法通用性不强，可用于积累思路。）

在给定的 $n$ 阶竞赛图中，每个顶点都有一个出度。由于图是有限的，必定存在一个出度最大的顶点，记为 $v$，其出度为 $d^+(v)$。

除 $v$ 外，其余顶点可以划分为两个互不相交的集合：

$A$：由所有被 $v$ 指向的顶点组成，因此 $|A|=d^+(v)$；
$B$：由所有指向 $v$ 的顶点组成。

由于该图是竞赛图，除 $v$ 外的每个顶点必定恰好属于 $A,B$ 中的一个。

对于任意 $x\in A$，存在有向边 $v\to x$，所以从 $v$ 到 $x$ 的有向路长度为 $1$。下面考虑任意 $y\in B$，只需证明存在 $x\in A$ 使 $x\to y$，此时 $v\to x\to y$ 的长度为 $2$。

反设不存在这样的 $x$。由于图是竞赛图，$A$ 中每个顶点与 $y$ 之间恰有一条有向边，所以必有 $y\to x$ 对所有 $x\in A$ 成立。又因为 $y\in B$，还有 $y\to v$。于是 $d^+(y)\geq|A|+1=d^+(v)+1>d^+(v)$，这与 $v$ 是出度最大的顶点矛盾。

因此，对于集合 $B$ 中的任意顶点 $y$，都存在至少一个集合 $A$ 中的顶点 $x$ 指向 $y$，从而构成长度为 $2$ 的有向路 $v\to x\to y$。故每个竞赛图中都存在一个顶点 $v$，使得 $v$ 到其余任意顶点都有一条长度至多为 $2$ 的有向路。

例题（3）

题目： 证明：每个竞赛图都有一条有向 Hamilton 路。

证明： 对竞赛图的顶点数 $n$ 使用第一数学归纳法。

当 $n=1$ 时，唯一的顶点自身构成一条平凡的有向 Hamilton 路；当 $n=2$ 时，两个顶点之间恰有一条有向边，该边构成一条经过全部顶点的有向 Hamilton 路。

假设任意 $k$ 阶竞赛图都存在有向 Hamilton 路。现设 $T$ 是一个 $k+1$ 阶竞赛图，从中任取一个顶点 $v$ 并暂时删除，得到 $k$ 阶子图 $T^{\prime}$。由归纳假设，$T^{\prime}$ 中存在有向 Hamilton 路 $v_1\to v_2\to\cdots\to v_k$。

把顶点 $v$ 重新加入，分三种情况讨论：

若 $v\to v_1$，则 $v\to v_1\to v_2\to\cdots\to v_k$ 是 $T$ 的有向 Hamilton 路。
若 $v_k\to v$，则 $v_1\to v_2\to\cdots\to v_k\to v$ 是 $T$ 的有向 Hamilton 路。
若以上两种情况都不成立，则 $v_1\to v$ 且 $v\to v_k$。沿序列 $v_1,v_2,\ldots,v_k$ 考察各顶点与 $v$ 之间有向边的方向，必存在某个 $i$（$1\leq i<k$），使得 $v_i\to v$ 且 $v\to v_{i+1}$。于是可以把 $v$ 插入 $v_i,v_{i+1}$ 之间，得到有向 Hamilton 路 $v_1\to\cdots\to v_i\to v\to v_{i+1}\to\cdots\to v_k$。

因此，任意 $k+1$ 阶竞赛图也存在有向 Hamilton 路。由第一数学归纳法，命题成立。

例题（4）

题目： 若具有 $n$ 个顶点的竞赛图强连通，且 $n\geq3$，则它含有一条有向 Hamilton 回路。

证明（反证法与最长回路法）： 根据竞赛图的基本性质，任何强连通竞赛图中都存在有向回路。在图 $T$ 的所有有向回路中，取一条长度最长的有向回路，设其长度为 $m$，记为 $C=v_1\to v_2\to\cdots\to v_m\to v_1$。只需证明 $m=n$。

假设 $m<n$，则图 $T$ 中存在顶点 $u\notin V(C)$。由 $T$ 的强连通性，回路 $C$ 上存在能够到达 $u$ 的顶点，同时 $u$ 也能够到达 $C$ 上的某个顶点。考察 $u$ 与 $C$ 上各顶点之间有向边的方向，可以找到回路上的一对相邻顶点 $v_i,v_{i+1}$，使得 $v_i\to u$ 且 $u\to v_{i+1}$。

于是，用有向路 $v_i\to u\to v_{i+1}$ 代替回路 $C$ 中的弧 $v_i\to v_{i+1}$，可得到一条长度为 $m+1$ 的有向回路： $$ v_1\to\cdots\to v_i\to u\to v_{i+1}\to\cdots\to v_m\to v_1. $$ 这与 $C$ 是最长有向回路矛盾。因此 $m<n$ 不成立，只能有 $m=n$。故 $C$ 是一条经过图中全部顶点的有向 Hamilton 回路。

数论基础

整除性与辗转相除

进入本门课程最后一章节——数论。此章说实话整体难度也比较大，需要对数论的各种结论和定理非常熟悉，且对数字有一定的敏感性，才可能解答出本章中较难的习题。作为数论开篇的基础，整除性与辗转相除主要介绍整除的许多性质以及辗转相除的两种方法，这些都是后面章节的基础，所以务必全部掌握。关于辗转相除，如果考试在大题而非简答题中考查，最好画表格写出过程；本节介绍的矩阵求解方法会用到诸如 $S_K$、$T_k$ 等公式。因此，第二种基于矩阵方法的公式最好也记住，但中间涉及线性代数矩阵的推导过程不必记忆，只需掌握结论中的公式及其用法。
对于本节中的定理：“任意两个整数 $a,b$ 的最高公因数 $d$ 可以表示为 $a,b$ 的倍数和，即 $d=sa+tb$，其中 $s,t$ 都是整数。”这个定理不是充要条件。必须先确定 $d$ 是 $a,b$ 的公因数，才能进一步推出其可表示为上述形式；反之，一个数能表示成 $a,b$ 倍数和的形式，不一定就是 $a,b$ 的最高公因数。若要将其表述为充要条件，应写为：正整数 $d$ 是 $a,b$ 的最高公因数，当且仅当 $d\mid a$ 且 $d\mid b$（即 $d$ 是 $a,b$ 的公因数），同时存在整数 $s,t$ 使 $d=sa+tb$。
关于最高公因数，因为最高公因数除符号外唯一确定，所以理论上正负形式都成立。但我记得老师说过，考试一般只写正的最高公因数即可得分，不需要同时写负的最高公因数。如果这里仍有不确定之处，可以再和任课老师确认。
注意一个特殊规定：任意整数都整除 $0$，特别地，$0$ 整除 $0$；但 $0$ 不能整除任意非零整数。

互质与质因数分解

本节互质和质因数分解是数论章节最重要、难度也最高的部分之一。压轴大题通常会涉及互质相关定理和条件的应用，而且条件和定理的用法很多，表示法也比较多，所以实际操作时常常会出现想不起来、想不到用哪个定理，或者看不出该用哪个定理的情况。这就要求对本节讲授的内容和定理多加熟悉与回顾，同时敢于练习较难、较灵活的题目，积累思路和手感。
$a$ 和 $b$ 互质，当且仅当 $1$ 可表示为 $a$ 和 $b$ 的倍数和，即存在整数 $s,t$，使 $1=sa+tb$。注意这个条件是充要条件，与上面第 6.1 节第 2 点所提到的定理不同。
本节所讲到的一个定理也是充要条件：$b$ 与 $a_1,a_2,\ldots,a_n$ 分别互质，当且仅当 $b$ 与 $a_1a_2\cdots a_n$ 互质。
总结一些同时与整除、互质有关的结论：

若 $a\mid b$，则 $a\mid bc$；若 $a\mid bc$，且 $a,c$ 互质，则 $a\mid b$。
若 $a\mid bc$，且 $a$ 为质数，则 $a\mid b$ 或 $a\mid c$。
若 $bc\mid a$，则 $b\mid a$、$c\mid a$；若 $b\mid a$、$c\mid a$，且 $b,c$ 互质，则 $bc\mid a$。
若 $a,b$ 互质且 $a,c$ 互质，则 $a$ 与 $bc$ 互质；反之亦成立。
质数 $p$ 与 $a$ 互质，当且仅当 $p\nmid a$。
任意两个不同的质数互质。
若 $p$ 整除 $a_1,a_2,a_3,\ldots,a_n$ 中的一个，则 $p\mid a_1a_2a_3\cdots a_n$。若要反向推导，必须加上 $p$ 为质数这一条件：若 $p\mid a_1a_2a_3\cdots a_n$ 且 $p$ 为质数，才可得 $p$ 整除其中某一个数。
$2^p-1$ 与 $2^q-1$ 互质的充要条件是 $p$ 与 $q$ 互质。（此结论在 PPT 中作为例题进行证明，我个人认为最好掌握该证明，因为它涉及后面马上要提到的一个技巧。虽然证明很难，但其难度接近期末真题，建议尽力掌握。）

关于 PPT 上的那几道例题，再强调一遍：如果想冲刺高分，最好务必掌握。数论相关证明题的起步难度本身就比较高，要学会适应这种难度。想取得高分，最好真正理解例题中的思路和方法；我认为它们大部分都很接近期末真题难度，有的甚至比期末题更难，建议尽量适应。
算术基本定理在 PPT 上给了三种形式，其实只需记住最完整的推论 2。注意 $0$ 和 $\pm1$ 不能用算术基本定理表示。算术基本定理在一些题中会用到，具体可以参见课后题以及《离散数学学习指导与习题解答》。此外，算术基本定理的欧几里得证明涉及一种构造法，后面的专题会介绍，最好有所掌握，以积累思路。
补充一些质因子相关结论：

设正整数 $a=p_1^{r_1}p_2^{r_2}\cdots p_k^{r_k}$，其中 $p_1,p_2,\ldots,p_k$ 是互不相同的质数，$r_1,r_2,\ldots,r_k$ 是正整数，则正整数 $d$ 为 $a$ 的因子的充要条件是 $d=p_1^{s_1}p_2^{s_2}\cdots p_k^{s_k}$，其中 $0\leq s_i\leq r_i$，$i=1,2,\ldots,k$。
若 $a$ 是合数，则 $a$ 必有一个不超过 $\sqrt a$ 的真因子。（任何大于 $1$ 的正整数除 $1$ 和它本身之外的因子称为真因子；此概念吉大教材没有，但北大版教材有相关介绍。）证明：因为 $a$ 是合数，所以 $a$ 可以分解为 $a=bc$，其中 $b>1$、$c>1$。$b$ 和 $c$ 不可能都大于 $\sqrt a$，否则 $bc>(\sqrt a)^2=a$，与 $bc=a$ 矛盾。因此，$b,c$ 中至少有一个不超过 $\sqrt a$，所以 $a$ 必有一个不超过 $\sqrt a$ 的真因子。
若 $a$ 是合数，则 $a$ 必有一个不超过 $\sqrt a$ 的质因子。证明：由上面的结论可知，$a$ 存在一个不超过 $\sqrt a$ 的真因子。若这个因子本身是质数，那么它就是 $a$ 的一个不超过 $\sqrt a$ 的质因子；若这个因子是合数，设其为 $b$，则 $b$ 必有一个质因子 $p$，于是 $p\leq b\leq\sqrt a$。又因为 $p\mid b$ 且 $b\mid a$，所以 $p\mid a$。因此，$a$ 必有一个不超过 $\sqrt a$ 的质因子。

梅森素数及其因式分解相关结论：

形如 $2^n-1$ 的数很有趣，因为近代已知的最大素数差不多总是形如 $2^n-1$ 的数。当 $n$ 为质数时，$2^n-1$ 既可能是质数，也可能是合数；当 $n$ 为质数且 $2^n-1$ 也是质数时，称 $2^n-1$ 为梅森素数。
若 $n$ 为合数，则 $2^n-1$ 必为合数。因为 $n$ 为合数，所以可以设 $n=ab$，其中 $a>1$、$b>1$。利用重要的因式分解 $2^n-1=2^{ab}-1=(2^a-1)(2^{a(b-1)}+2^{a(b-2)}+\cdots+2^a+1)$，由于等号右边的两个因子都大于 $1$，所以 $2^n-1$ 是合数。
对于任意正整数 $n$，有 $x^n-y^n=(x-y)(x^{n-1}+x^{n-2}y+x^{n-3}y^2+\cdots+xy^{n-2}+y^{n-1})$。
对于任意奇数 $n$，有 $x^n+y^n=(x+y)(x^{n-1}-x^{n-2}y+x^{n-3}y^2-\cdots-xy^{n-2}+y^{n-1})$。
二项式定理为 $(x+y)^n=\sum_{k=0}^{n}\binom{n}{k}x^{n-k}y^k$。
$x^{2^k}-1=(x-1)(x+1)(x^2+1)\cdots(x^{2^{k-1}}+1)$（费马数序列）。

最高公因数相关结论补充：除去最高公因数后所得两数互质。若 $d=(a,b)$，则存在整数 $k_1,k_2$，使 $a=k_1d$、$b=k_2d$，并且必有 $(k_1,k_2)=1$，即 $k_1,k_2$ 互质。证明：采用反证法。假设 $(k_1,k_2)>1$，则存在整数 $t>1$，使 $t\mid k_1$ 且 $t\mid k_2$。因为 $a=k_1d$、$b=k_2d$，所以 $dt\mid a$ 且 $dt\mid b$，即 $dt$ 是 $a,b$ 的公因数。但是 $t>1$，所以 $dt>d$，这与 $d$ 是 $a,b$ 的最高公因数矛盾。因此假设不成立，故 $(k_1,k_2)=1$。
关于高次幂互质或整除的结论补充：

互质整数的正整数次幂仍然互质：若 $(a,b)=1$，则对于任意正整数 $m,n$，都有 $(a^m,b^n)=1$。这可以对定理“$b$ 与 $a_1,a_2,\ldots,a_n$ 分别互质，当且仅当 $b$ 与 $a_1a_2\cdots a_n$ 互质”使用两次得到。
若 $a\mid b$，则对于任意正整数 $n$，都有 $a^n\mid b^n$。

合同与一次同余式

合同这一节也是重点考点。和整除与互质一样，需要熟悉合同的各种性质。期末数论压轴题看似是整除或互质问题时，若能采用合同的形式表达，有时会产生奇效。另外，一次合同方程组的求解期末基本上必考，但它其实是套路题，只要按照 PPT 的方法练习，通常没有问题。
本节补充两个结论：

结论一： 若 $a_0,a_1,\ldots,a_{m-1}$ 是模 $m$ 的一个完全剩余系，且 $\gcd(b,m)=1$，则 $ba_0,ba_1,\ldots,\allowbreak ba_{m-1}$ 也是模 $m$ 的一个完全剩余系。

证明： 只需证明 $ba_0,ba_1,\ldots,\allowbreak ba_{m-1}$ 两两模 $m$ 不同余。任取 $i\ne j$，反设 $ba_i\equiv ba_j\pmod m$，则 $m\mid b(a_i-a_j)$。因为 $\gcd(b,m)=1$，所以由同余式的消去律可得 $m\mid(a_i-a_j)$，即 $a_i\equiv a_j\pmod m$。但 $a_0,a_1,\ldots,a_{m-1}$ 是模 $m$ 的完全剩余系，因此当 $i\ne j$ 时必有 $a_i\not\equiv a_j\pmod m$，矛盾。所以 $ba_0,ba_1,\ldots,\allowbreak ba_{m-1}$ 两两模 $m$ 不同余。由于它们共有 $m$ 个数，分别属于模 $m$ 的 $m$ 个不同剩余类，因此 $ba_0,ba_1,\ldots,\allowbreak ba_{m-1}$ 构成模 $m$ 的一个完全剩余系。证毕。
结论二： 设 $r_1,r_2,\ldots,r_{\varphi(m)}$ 是模 $m$ 的一个简化剩余系，固定 $i\in\lbrace1,2,\ldots,\varphi(m)\rbrace$，且 $x_0$ 是同余方程 $r_i x\equiv1\pmod m$ 的一个解。证明：存在某个 $j\in\lbrace1,2,\ldots,\varphi(m)\rbrace$，使 $x_0\equiv r_j\pmod m$。

证明： 由 $r_i x_0\equiv1\pmod m$ 可知 $m\mid(r_i x_0-1)$，所以存在整数 $q$，使 $r_i x_0-mq=1$。若整数 $d$ 同时整除 $x_0$ 和 $m$，则 $d\mid r_i x_0$ 且 $d\mid mq$，从而 $d\mid(r_i x_0-mq)=1$，因此 $d=1$。所以 $\gcd(x_0,m)=1$。这说明 $x_0$ 所在的模 $m$ 剩余类是一个简化剩余类。由于 $r_1,r_2,\ldots,r_{\varphi(m)}$ 是模 $m$ 的简化剩余系，它们恰好代表模 $m$ 的全部简化剩余类，因此存在唯一的 $j\in\lbrace1,2,\ldots,\varphi(m)\rbrace$，使 $x_0\equiv r_j\pmod m$。证毕。

秦九韶定理与欧拉函数

本节一般来说在大一下学期不会考。因为各位离散数学老师的授课进度不同，有的讲得快，有的讲得慢，所以通常会以进度最慢的老师为准。进度最慢的老师一般到结课时只能完整讲完“合同与一次同余式”，而讲不完“秦九韶定理与欧拉函数”，因此本节大概率不在离散数学Ⅰ期末考试中考查。不过，本节也可能放到离散数学Ⅱ中考查，25 级就是这种情况。就本节的难度和重点而言，秦九韶定理按照 PPT 练习即可，属于完全的套路题，弄懂 PPT 上的例题就能明白。欧拉函数方面则有可能出现证明题，包括费马-欧拉定理以及费马小定理的推论等；既然有可能考证明，最好把书上课后题过一遍。另外，费马-欧拉定理还提供了一种求解一次同余式组的新思路，课后题中也有，可以了解。

数论证明题整理与总结

数论证明题同样抽象，难度也比较高，需要在结论、方法和具体题型之间反复梳理。数论部分在《离散数学学习指导与习题解答》中题型很多、类型很全，这里主要记录我认为值得回看的方法和思路，整理程度可能不如图论完整。由于不少题型并不能用一种通用方法概括，一些特殊方法没有全部收录；遇到具体问题时，可以结合课后题和习题解答继续复盘。

我在《离散数学学习指导与习题解答》数论章节中标记的参考题：

5.2.1—5.2.5 的所有例题；5.3.1 中除第 3、4、6 题以外的题；5.3.2 中除第 1、2、4、8、13、14、15 题以外的题；5.3.3 中除第 5、6、7、8 题以外的题；5.3.4 中第 1、2、5、9、10 题可以做。

方法整理

阅读下面的方法前，我会先回顾 PPT 上以及前文补充的整除、互质和合同性质；后面的证明题会反复用到这些基础结论。

梅森素数与因式分解

梅森素数与一些因式分解公式已经在前面的互质部分介绍，这里记录两道相关证明，方便之后复盘。

例题（1）

题目： 证明：当 $n>2$ 且 $n\in\mathbb{Z}$ 时，$2^n-1$ 与 $2^n+1$ 中至少有一个是合数。（24 级软件学院离散数学Ⅰ真题）

证明： 根据 $n$ 是合数还是质数，分两种情况讨论。

第一种情况：$n$ 是合数。 因为 $n$ 是合数，所以存在整数 $a>1$ 和 $b>1$，使 $n=ab$。由前面的因式分解公式可得 $2^n-1=(2^a-1)(2^{a(b-1)}+2^{a(b-2)}+\cdots+2^a+1)$。由于 $a>1$ 且 $b>1$，等号右边的两个因数都大于 $1$，所以 $2^n-1$ 是合数。

第二种情况：$n$ 是质数。 因为 $n>2$，所以 $n$ 必为奇数，$n-1$ 必为合数。于是存在正整数 $k$，使 $n-1=2k$，即 $n=2k+1$。此时 $2^n+1=2^n+2-1=2(2^{n-1}+1)-1=2(2^{n-1}-1+2)-1=2(2^{2k}-1+2)-1$。又因为 $2^{2k}-1=4^k-1=(4-1)(4^{k-1}+4^{k-2}+\cdots+4+1)=3(4^{k-1}+4^{k-2}+\cdots+4+1)$，所以 $2^n+1=2[3(4^{k-1}+4^{k-2}+\cdots+4+1)+2]-1=6(4^{k-1}+4^{k-2}+\cdots+4+1)+3=3[2(4^{k-1}+4^{k-2}+\cdots+4+1)+1]$。由于 $k\geq1$，所以 $2(4^{k-1}+4^{k-2}+\cdots+4+1)+1>1$，故 $2^n+1$ 是合数。

综上，两者至少有一个是合数。

可见，这道题主要利用了合数的定义以及前面介绍的梅森数因式分解公式。它也可以尝试用合同的方法证明，之后可以作为一种不同思路进行练习。

例题（2）

题目： 证明：对正整数 $a,b$，恒有 $\gcd(2^a-1,2^b-1)=2^{\gcd(a,b)}-1$。

证明： 先回顾最大公因数的基本性质：对于任意整数 $x,y,q$，都有 $\gcd(x,y)=\gcd(y,x-qy)$。这是因为，若一个整数同时整除 $x$ 和 $y$，那么它也整除 $x-qy$；反过来，若一个整数同时整除 $y$ 和 $x-qy$，那么它也整除 $(x-qy)+qy=x$。因此，这两组数的公因数完全相同，最大公因数也相同。

不妨设 $a\geq b$。对 $2^a-1$ 和 $2^b-1$ 使用上述性质，有 $\gcd(2^a-1,2^b-1)=\gcd\bigl(2^b-1,(2^a-1)-2^{a-b}(2^b-1)\bigr)$。计算第二个数可得 $(2^a-1)-2^{a-b}(2^b-1)=2^a-1-(2^a-2^{a-b})=2^{a-b}-1$，所以 $\gcd(2^a-1,2^b-1)=\gcd(2^b-1,2^{a-b}-1)$。这说明，在不改变最大公因数的情况下，可以把指数对 $(a,b)$ 变成 $(b,a-b)$，正好与求 $\gcd(a,b)$ 时使用的辗转相除法相对应。例如，若 $a=qb+r$，其中 $0\leq r<b$，那么连续进行 $q$ 次上述运算，就可以得到 $\gcd(2^a-1,2^b-1)=\gcd(2^b-1,2^r-1)$。

下面对指数 $a,b$ 使用辗转相除法。设 $a=q_1b+r_1$，其中 $0\leq r_1<b$；$b=q_2r_1+r_2$，其中 $0\leq r_2<r_1$；$r_1=q_3r_2+r_3$；依此类推，直到得到 $r_{s-1}=q_{s+1}r_s$。辗转相除法告诉我们，最后一个非零余数就是 $a$ 与 $b$ 的最大公因数，即 $r_s=\gcd(a,b)$。

按照前面得到的指数缩减公式，依次有 $\gcd(2^a-1,2^b-1)=\gcd(2^b-1,2^{r_1}-1)$，$\gcd(2^b-1,2^{r_1}-1)=\gcd(2^{r_1}-1,2^{r_2}-1)$，继续进行下去，最终得到 $\gcd(2^a-1,2^b-1)=\gcd(2^{r_s}-1,2^0-1)$。因为 $2^0-1=0$，而任意正整数与 $0$ 的最大公因数等于它本身，所以 $\gcd(2^{r_s}-1,0)=2^{r_s}-1$。又因为 $r_s=\gcd(a,b)$，所以 $\gcd(2^a-1,2^b-1)=2^{r_s}-1=2^{\gcd(a,b)}-1$。

这道题与互质部分 PPT 中的结论“$2^p-1$ 与 $2^q-1$ 互质的充要条件是 $p$ 与 $q$ 互质”的证明过程很像。两者均是梅森数形式，证明过程也都使用了辗转相除法。这个方法的通用性不算特别强，但其中的证明思路值得记下来。

费马数序列

详见课后题例 5.2.12 和 5.3.2 第 16 题。

按模分类的思想

例题 5.2.4、例题 5.2.5、5.3.3 第 4 题（Wilson 定理）尤其经典。还有各种数论小题，例如证明整除的题型，其中“连续三个整数必有一个能被 $3$ 整除”等技巧，都是按模分类的思想。

这里再补充一道题。

题目： 设整数 $a,b,c$ 满足 $a^2+b^2=c^2$，证明：$a,b$ 中至少有一个能被 $3$ 整除。

证明： 对任意整数 $x$，按照除以 $3$ 的余数分类，只有以下三种情况：

若 $x\equiv0\pmod3$，则 $x^2\equiv0^2\equiv0\pmod3$；
若 $x\equiv1\pmod3$，则 $x^2\equiv1^2\equiv1\pmod3$；
若 $x\equiv2\pmod3$，则 $x^2\equiv2^2\equiv4\equiv1\pmod3$。

因此，任意整数的平方除以 $3$ 的余数只能是 $0$ 或 $1$，不可能是 $2$。也就是说，对任意整数 $x$，都有 $x^2\equiv0$ 或 $1\pmod3$。

下面用反证法。假设 $a,b$ 都不能被 $3$ 整除，即 $3\nmid a$ 且 $3\nmid b$。因为 $a$ 不能被 $3$ 整除，所以 $a\equiv1$ 或 $2\pmod3$，从而 $a^2\equiv1\pmod3$；同理，$b^2\equiv1\pmod3$。于是由 $a^2+b^2=c^2$ 可得 $c^2=a^2+b^2\equiv1+1\equiv2\pmod3$。但前面已经证明，任何整数的平方模 $3$ 只可能余 $0$ 或 $1$，不可能余 $2$，产生矛盾。

所以假设错误，$a,b$ 不可能都不被 $3$ 整除。因此，$a,b$ 中至少有一个能被 $3$ 整除，即 $3\mid a$ 或 $3\mid b$。

构造性证明

PPT 上关于质数无穷多的证明，以及例 5.2.11、5.3.2 第 5 题、5.3.2 第 6 题、5.3.2 第 7 题，都是通过直接构造题目中假定不存在的对象，再使用反证法证明命题正确。这种思路不容易想到，通用性也不强，积累思路即可。

关于 5.3.2 第 6 题和第 7 题的思路，需要着重强调。证明形如 $dn+d-1$ 的质数有无穷多个，通常有固定思路：（1）先假设只有有限个这样的质数，然后构造 $N=dp_1p_2\cdots p_n+d-1$；（2）证明 $d$ 的所有因子都不是 $N$ 的因子，即使用按模分类的思想；（3）根据完全剩余系指出 $N$ 中必定存在形如 $dn+d-1$ 的因子；（4）指出所有形如 $dn+d-1$ 的数 $p_1,p_2,\ldots,p_m$ 都不是 $N$ 的因子，从而得到矛盾，命题得证。具体这一流程如何在题中体现，一定要查看对应解答。

算术基本定理与最小质因数

算术基本定理这里不再重复举例。在课后题与习题解答中，许多证明题都会用到它。这个定理的主要作用，是把任意一个除 $0,\pm1$ 以外的整数唯一地表示出来，从而可以在该表达式上进行分析。至于最小质因数法，则是建立在算术基本定理上的一种证明手段。前面提到的构造性证明中，例 5.2.11 就使用了这种方法：通过算术基本定理知道所构造的 $N$ 有一个最小质因数 $p$，再以 $p$ 为桥梁进行分析，得到欲证命题。下面用两道题记录最小质因数法配合算术基本定理的使用。

例题（1）

题目： 若正整数 $n$ 满足 $n\mid 2^n-1$，证明：$n=1$。

证明： 显然，当 $n=1$ 时，有 $1\mid2^1-1$，所以 $n=1$ 确实满足条件。下面证明不存在 $n>1$ 的情况。

反设 $n>1$。由算术基本定理，$n$ 可以唯一分解为若干素数的乘积，因此 $n$ 一定存在最小素因数，记为 $p$。因为 $p\mid n$，且题设给出 $n\mid2^n-1$，所以 $p\mid2^n-1$，即 $2^n\equiv1\pmod p$。注意到 $2^n-1$ 是奇数，因此 $n$ 不可能是偶数；否则 $2\mid n$ 会推出 $2\mid2^n-1$，与 $2^n-1$ 为奇数矛盾。所以 $p\neq2$，即 $p$ 是奇素数。设 $r$ 是使同余式 $2^r\equiv1\pmod p$ 成立的最小正整数。由于 $2^n\equiv1\pmod p$，这样的 $r$ 一定存在。首先，$r>1$；若 $r=1$，则 $2\equiv1\pmod p$，从而 $p\mid1$，不可能成立。

第一步：证明 $r\mid n$。 对 $n$ 除以 $r$，由带余除法可写成 $n=qr+s$，其中 $0\leq s<r$。于是 $2^n=2^{qr+s}=(2^r)^q2^s$。因为 $2^r\equiv1\pmod p$，所以 $2^n\equiv2^s\pmod p$。另一方面，已经知道 $2^n\equiv1\pmod p$，因此 $2^s\equiv1\pmod p$。如果 $s>0$，那么 $0<s<r$，这与 $r$ 是满足 $2^r\equiv1\pmod p$ 的最小正整数矛盾。因此只能有 $s=0$，从而 $r\mid n$。

第二步：证明 $r\mid p-1$。 因为 $p$ 是奇素数，并且 $p\nmid2$，由费马小定理可得 $2^{p-1}\equiv1\pmod p$。对 $p-1$ 除以 $r$，写成 $p-1=ur+t$，其中 $0\leq t<r$。于是 $2^{p-1}=2^{ur+t}=(2^r)^u2^t\equiv2^t\pmod p$。又因为 $2^{p-1}\equiv1\pmod p$，所以 $2^t\equiv1\pmod p$。由 $r$ 的最小性可知 $t=0$，因此 $r\mid p-1$，所以 $r\leq p-1<p$。

第三步：利用最小质因数产生矛盾。 前面已经证明 $r\mid n$，并且 $r>1$。由算术基本定理，$r$ 至少有一个素因数，记为 $q$。因为 $q\mid r$ 且 $r\mid n$，所以 $q\mid n$，即 $q$ 也是 $n$ 的素因数。由于 $p$ 是 $n$ 的最小素因数，因此 $q\geq p$。另一方面，因为 $q\mid r$，所以 $q\leq r$，从而 $r\geq q\geq p$。但前面又得到 $r<p$，产生矛盾。因此，假设 $n>1$ 不成立，唯一可能是 $n=1$。

例题（2）

题目： 设正整数 $a,b$ 互质，且 $a$ 是奇数、$b$ 是偶数。证明：$a+b$ 与 $a^2+b^2$ 互质。（25 级软件学院离散数学Ⅰ真题）

方法一：最小质因数与算术基本定理。 反设 $a+b$ 与 $a^2+b^2$ 不互质，即 $\gcd(a+b,a^2+b^2)>1$。根据算术基本定理，任何大于 $1$ 的整数都可以分解为素数的乘积，因此 $\gcd(a+b,a^2+b^2)$ 一定有素因数。取其中最小的素因数，记为 $p$，则 $p\mid(a+b)$，且 $p\mid(a^2+b^2)$。因为 $a$ 是奇数、$b$ 是偶数，所以 $a+b$ 是奇数。由于 $p\mid(a+b)$，所以 $p$ 也是奇数，从而 $p\neq2$，即 $p\nmid2$。又因为 $p\mid(a+b)$，所以 $p$ 也整除 $(a+b)(a-b)$。于是 $p$ 同时整除 $a^2+b^2$ 和 $(a+b)(a-b)$，因此 $p$ 整除二者之差 $p\mid[(a^2+b^2)-(a+b)(a-b)]$。注意到 $(a+b)(a-b)=a^2-b^2$，所以 $(a^2+b^2)-(a+b)(a-b)=2b^2$，因此 $p\mid2b^2$。由于 $p$ 是素数且 $p\nmid2$，所以 $p\mid b^2$，进而 $p\mid b$。另一方面，已经知道 $p\mid(a+b)$，又有 $p\mid b$，所以 $p\mid[(a+b)-b]$，即 $p\mid a$。于是 $p$ 同时整除 $a$ 和 $b$，从而 $p\mid\gcd(a,b)$。但题设给出 $\gcd(a,b)=1$，与素数 $p>1$ 矛盾。因此，反设不成立，故 $\gcd(a+b,a^2+b^2)=1$。

方法二：同余。 设 $d=\gcd(a+b,a^2+b^2)$，要证明 $d=1$。反设 $d>1$。根据算术基本定理，$d$ 至少含有一个素因数，取其中一个素因数记为 $p$。于是 $p\mid(a+b)$，且 $p\mid(a^2+b^2)$。因此 $a+b\equiv0\pmod p$，即 $a\equiv-b\pmod p$；将两边平方，得到 $a^2\equiv b^2\pmod p$。另一方面，由 $p\mid(a^2+b^2)$，可得 $a^2+b^2\equiv0\pmod p$。把 $a^2\equiv b^2\pmod p$ 代入，得到 $2b^2\equiv0\pmod p$。由于 $a$ 是奇数、$b$ 是偶数，所以 $a+b$ 是奇数；又因为 $p\mid(a+b)$，所以 $p$ 必为奇素数，即 $p\neq2$。因此 $2$ 在模 $p$ 意义下可以消去，从而 $b^2\equiv0\pmod p$。因为 $p$ 是素数，所以由 $p\mid b^2$ 可得 $p\mid b$，即 $b\equiv0\pmod p$。再由 $a\equiv-b\pmod p$，可得 $a\equiv0\pmod p$，所以 $p\mid a$。于是 $p$ 同时整除 $a$ 和 $b$，这与题设 $\gcd(a,b)=1$ 矛盾。因此假设 $d>1$ 不成立，只能有 $\gcd(a+b,a^2+b^2)=1$。

由此可以看到，如果一道证明题使用传统的整除或互质相关定理没有思路，可以尝试向合同、同余的思路靠拢。它实际上是换了一种表达方式，在新的表达体系下有新的定理可以使用，或许能够开拓思路。

奇数与偶数

看到题中说某个数是奇数或不能被 $2$ 整除，应立即想到该数可以等价地表示为 $2k+1$ 或 $2k-1$（两种表达等价，$k$ 为整数）；如果某个数是偶数，则可以等价地表示为 $2k$。很多题都是利用奇偶性的等价表达解决的，但也有例外，例如上面那道真题就不需要写出奇数和偶数的等价表达，关键在于使用其他方法证明。因此，对这种等价表达有印象即可，不要过于死板。

例 5.2.6 是一个典型。