"有欧拉回路的图必有 Hamiltonian 回路，反之亦然。"
两者相互独立。欧拉回路要求每条边恰好一次，Hamiltonian 回路要求每个顶点恰好一次。\(Q_3\) 有 Hamiltonian 回路但无欧拉回路（度 3 奇）；8字形图（两个三角形共顶点）有欧拉回路但无 Hamiltonian 回路。
CS70 · 第 4 讲
本讲整理图论的核心结构与证明技巧：从欧拉迹/回路的度数判定、握手定理与奇度顶点计数，到二分图判定与树的性质、超立方体的哈密顿/欧拉性、平面图与 K₅/K₃,₃ 判定、边染色算法；并引入模运算初步（模方程、Wilson 定理、Fermat 小定理、Euler 函数），为 RSA 与后续数论铺垫。讲义按概念依赖组织，不以 PDF 页序堆砌。
设 \(G=(V,E)\) 为无向图（允许孤立顶点）。一条欧拉迹（Eulerian walk）是经过每条边恰好一次的行走；若起点与终点重合，则称欧拉回路（Eulerian tour）。行走的"经过边恰好一次"是本节所有讨论的核心约束。
定理（Euler）。 设 \(G\) 无向，则 \[ G\text{ 有欧拉回路 } \iff G\text{ 连通（除孤立顶点外）且所有顶点度数为偶。} \] \[ G\text{ 有欧拉迹（不必闭合） } \iff G\text{ 连通（除孤立顶点外）且奇度顶点个数为 }0\text{ 或 }2。 \] "必要性（\(\implies\)）：若存在欧拉迹，每次进入一个中间顶点必伴随一次离开，因此中间顶点贡献偶数条关联边，度数必为偶。只有起点与终点可能奇度，且二者重合时全图无奇度顶点。所有被经过的边连通到同一条迹上，故非孤立顶点彼此连通。
"充分性（\(\impliedby\)）：若全图偶度且连通，课堂上已给 FindTour 算法（通过 splicing 合并子回路）构造欧拉回路。若恰有两个奇度顶点 \(u,v\)，可添加辅助顶点 \(w\) 与边 \(\{u,w\},\{w,v\}\) 得到全偶度图 \(G'\)，在 \(G'\) 上跑欧拉回路后删去 \((u,w),(w,v)\) 两段，即得 \(G\) 上从 \(u\) 到 \(v\) 的欧拉迹。另一种构造：取 \(u\)-\(v\) 路径删去，使剩余图各连通分支均为欧拉图，再把各分支回路与路径在公共顶点处缝合。
Hamiltonian 对比。 Hamiltonian 回路要求每个顶点恰好访问一次，与欧拉（每条边恰好一次）是两类问题。超立方体总有 Hamiltonian 回路（见 §3），但欧拉回路仅当 \(n\) 偶——说明两类周游的判定难度截然不同。
考虑图 \(G\) 的顶点 \(V=\{A,B,C,D,E\}\)，边 \(E=\{AB,AC,AD,BC,BD,CE,DE\}\)。各顶点度数：\(\deg(A)=3,\deg(B)=3,\deg(C)=3,\deg(D)=3,\deg(E)=2\)。奇度顶点为 \(A,B,C,D\) 共 4 个，\(G\) 连通。由定理，\(G\) 既无欧拉回路（奇度 \(\neq 0\)），也无欧拉迹（奇度 \(=4>2\)）。若删去边 \(CD\)，则 \(\deg(C)=2,\deg(D)=2\)，奇度仅剩 \(A,B\)，此时存在一条从 \(A\) 到 \(B\) 的欧拉迹；若进一步删去 \(BC\)，则全图偶度且仍连通，可得欧拉回路。此例显示：奇度顶点数是"0 或 2"这一窄窗口直接决定了迹/回路的存在性。
握手定理（Handshaking Lemma）。 对任意无向图 \(G=(V,E)\)： \[ \sum_{v\in V}\deg(v)=2|E|. \] 每条无向边 \(\{u,v\}\) 在求和中贡献两次（\(u,v\) 各一次），故总和为边数的 2 倍。
推论。 \(G\) 中奇度顶点的个数必为偶。设 \(V_{\text{odd}}\) 为奇度顶点集，则 \(|V_{\text{odd}}|\) 为偶。
证法 (i) 直接计数。 将求和拆为奇度项与偶度项： \[ \sum_{v\in V_{\text{odd}}}\deg(v)=2|E|-\sum_{v\notin V_{\text{odd}}}\deg(v). \] 右端两项均为偶（\(2|E|\) 偶，偶度顶点求和仍偶），故左端偶。而左端每一项 \(\deg(v)\) 都奇，奇数个奇数之和才奇，因此项数 \(|V_{\text{odd}}|\) 必偶。
证法 (ii) 对 \(m=|E|\) 归纳。 基例 \(m=0\) 全零度，\(V_{\text{odd}}=\emptyset\) 偶。归纳步：从 \(G\)（\(m+1\) 边）删去一边 \(\{u,v\}\) 得 \(G'\)，\(u,v\) 的奇偶性翻转、其余不变，故 \(|V_{\text{odd}}(G)|-|V_{\text{odd}}(G')|\in\{-2,0,2\}\)。由归纳假设 \(|V_{\text{odd}}(G')|\) 偶，得 \(|V_{\text{odd}}(G)|\) 偶。
证法 (iii) 对 \(n=|V|\) 归纳。 删去顶点 \(v\) 及其关联边得 \(G'\)，\(v\) 的邻居中奇度变偶、偶度变奇，\(v\) 自身是否奇度取决于 \(|N(v)|\)。分 \(|N(v)|\) 偶/奇两种情形，均可将 \(|V_{\text{odd}}(G)|\) 写成 \(|V_{\text{odd}}(G')|+|N(v)|-2|A|\) 或加 1 的形式，由归纳假设与 \(|N(v)|\) 奇偶性得偶。此证法较繁琐，说明"对正确变量归纳"能显著简化证明。
设 \(G\) 有顶点 \(\{1,2,3,4,5\}\)，边 \(\{12,13,14,23,45\}\)。度数序列 \(3,2,2,2,1\)，\(|E|=5\)，\(\sum\deg=10=2|E|\)。\(V_{\text{odd}}=\{1,5\}\)，个数为 2（偶）。用证法 (ii)：删去 \(\{45\}\) 得 \(G'\)，\(\deg_{G'}(4)=1,\deg_{G'}(5)=0\)，奇度集变为 \(\{1,4\}\)，个数仍为 2，差值 \(0\in\{-2,0,2\}\)。
定义。 无向图 \(G=(V,E)\) 是二分图，若存在划分 \(V=L\cup R\)（\(L\cap R=\emptyset\)）使得每条边两端分别在 \(L,R\)。等价地，\(G\) 可 2-染色（相邻顶点不同色）。
定理。 \(G\) 二分 \(\iff G\) 不含奇圈。
证明。"\(\implies\)"： 设 \(G\) 二染色。任取圈 \(v_0v_1\dots v_{k-1}v_0\)，沿圈颜色交替，故回到起点需偶数步，\(k\) 必偶，无奇圈。
"\(\impliedby\)"： 对每个连通分支从任意根做 BFS，按深度奇偶分 \(L,R\)。若存在同色相邻边 \(\{u,v\}\)，则 \(u,v\) 深度差为偶，加上该边构成奇圈，矛盾。故 BFS 染色成功，\(G\) 二分。
推论。 所有树都是二分图。树无圈，当然无奇圈，由定理即二分。也可归纳证：\(n=2\) 显然；对 \(n+1\) 顶树去掉一叶得 \(n\) 顶二分树，叶放邻点异侧即可。
判定算法。 用 BFS/DFS 2-染色，\(|V|+|E|\) 时间；遇同色邻边即判非二分。
路径树 \(P_4\)：\(1-2-3-4\)。BFS 从 1 染色：\(L=\{1,3\},R=\{2,4\}\)，每条边跨 \(L,R\)，二分。若加边 \(\{1,3\}\) 得圈 \(1-2-3-1\)（长度 3，奇），则 BFS 中 1 与 3 同色（都在 \(L\)），加边即冲突，判为非二分。
\(n\) 维超立方体 \(Q_n\)。 顶点 \(V=\{0,1\}^n\)，\(x\sim y \iff x,y\) 恰相差一位。\(|V|=2^n\)，\(|E|=n2^{n-1}\)，每顶点度 \(n\)，\(Q_n\) 连通（逐位翻转可达）。
二分性。 按位 1 的个数奇偶分 \(L,R\)，每条边翻一位，奇偶变号，故 \(Q_n\) 二分。
Hamiltonian 回路。 归纳构造：\(Q_1\) 为 \(0,1\) 回路。\(Q_{n+1}\) 由两个 \(Q_n\)（前导 0/1）组成。先在 0-子立方跑 Hamiltonian 路径 \(x_0\dots y_0\)（不闭），跨到 1-子立方 \(y_1\)，反向跑路径到 \(x_1\)，再闭合回 \(x_0\)。所得序列即 Gray 码。
欧拉回路。 \(Q_n\) 每点度 \(n\)，连通，故由 Euler 定理：欧拉回路存在 \(\iff n\) 偶。
平面图。 无向图 \(G\) 平面若可画在平面上使边仅在顶点处相交。必要条件（\(v\ge 3\)）： \[ |E|\le 3|V|-6\quad\text{（若二分则 }|E|\le 2|V|-4\text{）} \] 由欧拉公式 \(v-e+r=2\)（\(r\) 为面数）及每面至少 3 边（二分时至少 4 边）推导。
Kuratowski 定理。 \(G\) 平面 \(\iff G\) 不含 \(K_5\) 或 \(K_{3,3}\) 的细分。
补图反例。 对 \(v\ge 15\)，\(G\) 平面 \(\implies \bar G\) 非平面（由 \(e\le 3v-6\) 推出 \(\bar e>3v-6\)），但其逆不成立：取 \(G\) 含 \(K_5\) 加 10 个孤立点，则 \(G,\bar G\) 均含 \(K_5\)，同为非平面。
\(Q_2\)：顶点 \(00,01,11,10\)，Gray 码 \(00\to01\to11\to10\to00\) 为 Hamiltonian 回路；每点度 2（偶），亦为欧拉回路。\(Q_3\) 每点度 3（奇），有 Hamiltonian 回路 \(000,001,011,010,110,111,101,100\) 但无欧拉回路。平面图反例：\(v=15\)，\(G=K_5\cup 10K_1\)，\(\bar G\) 在另 5 个孤立点上构成 \(K_5\)，二者均含 \(K_5\)，同非平面，否定"\(\bar G\) 平面"的逆命题。
定义。 图 \(G\) 的边染色给每条边分配颜色，使共顶点的边不同色。边色数 \(\chi'(G)\) 为最少所需颜色数。最大度记 \(d=\max_v\deg(v)\)。
定理 1（贪心上界）。 任意图 \(G\) 可 \(2d-1\) 边染色。
证明（对边数归纳）。 基例 0 边显然。删一边 \(e\) 得 \(G'\)，由归纳假设 \(G'\) 可 \(2d'-1\)（\(\le 2d-1\)）染色。\(e\) 两端各至多 \(d-1\) 条邻边已染色，至多 \(2(d-1)=2d-2\) 色被禁，\(2d-1\) 色中至少一色可用。
定理 2（树的精确界）。 树 \(T\) 可 \(d\) 边染色（\(\chi'(T)=d\)）。
证明（对顶点数归纳）。 删一叶 \(v\) 得 \(T'\)，由归纳假设 \(T'\) \(d\) 染色。\(v\) 的邻点 \(u\) 在 \(T'\) 中度 \(\le d-1\)，故 \(u\) 的邻边至多占 \(d-1\) 色，\(d\) 色中至少一色可染 \(\{u,v\}\)。
Vizing 定理（陈述）。 任意简单图满足 \(d\le\chi'(G)\le d+1\)。\(\chi'(G)=d\) 称 Class 1，\(=d+1\) 称 Class 2。树与偶环为 Class 1；奇环 \(C_{2k+1}\) 为 Class 2。
星形树 \(K_{1,4}\)：中心度 4，叶度 1，\(d=4\)。定理 2 保证 4 色可染：中心四条边各一色，叶无冲突。\(K_4\)（\(d=3\)）可 3 边染色（Class 1）：先三角形 \(u_1u_2u_3\) 用色 1,2,3，再加顶点 \(v\) 对三条边依次选不冲突色，\(2d-1=5\) 的宽松上界远非紧，但证明简洁且对任意图通用。
模 \(m\) 方程。 \(ax\equiv b\pmod m\) 有解 \(\iff \gcd(a,m)\mid b\)。若 \(\gcd(a,m)=1\)，则 \(a\) 有唯一逆元 \(a^{-1}\pmod m\)（由扩展 Euclid 求得），解为 \(x\equiv a^{-1}b\pmod m\)。例如 \(9x+5\equiv7\pmod{13}\implies9x\equiv2\pmod{13}\)，\(9^{-1}\equiv3\pmod{13}\)，故 \(x\equiv6\pmod{13}\)。若 \(\gcd(a,m)\nmid b\) 则无解，如 \(3x+12\equiv4\pmod{21}\) 两边模 3 得 \(0\equiv1\pmod3\)，矛盾。
Wilson 定理。 对整数 \(p>1\)： \[ (p-1)!\equiv-1\pmod p\iff p\text{ 是素数。} \] "\(\implies\)"：\(p\) 素数。\(1,\dots,p-1\) 中，逆元是自身的仅 \(1,p-1\)（因 \(x^2\equiv1\pmod p\implies x\equiv\pm1\)）。其余数配成 \((p-3)/2\) 对互逆元，每对积为 1，故 \((p-1)!\equiv1\cdot(p-1)\cdot1\equiv-1\pmod p\)。 "\(\impliedby\)"：\(p\) 合数，设 \(q\) 为 \(p\) 的素因子（\(2\le q\le p-2\)）。\((p-1)!\) 含因子 \(q\)，故 \((p-1)!\equiv0\pmod q\)。若 \((p-1)!\equiv-1\pmod p\)，则 \((p-1)!\equiv-1\pmod q\)，\(0\equiv-1\pmod q\) 矛盾。 Fermat 小定理（FLT）。 若 \(p\) 素数且 \(\gcd(a,p)=1\)，则 \[ a^{p-1}\equiv1\pmod p。 \] 证：\(a,2a,\dots,(p-1)a\) 是 \(1,\dots,p-1\) 的排列（模 \(p\)），求积得 \(a^{p-1}(p-1)!\equiv(p-1)!\pmod p\)，约去 \((p-1)!\)（与 \(p\) 互素）即得。 Euler 函数。 \(\varphi(m)=|\{1\le a\le m:\gcd(a,m)=1\}|\)。若 \(p\) 素数，\(\varphi(p)=p-1\)。Euler 定理： \(\gcd(a,m)=1\implies a^{\varphi(m)}\equiv1\pmod m\)，是 FLT 的推广。这些是 RSA 加解密的数论基础。
Wilson 应用：\(p=7\)，\(6!=720\equiv-1\pmod7\)（\(720=7\cdot103-1\)），判 7 素数。\(p=8\) 合数，\(7!=5040\equiv0\pmod8\)，不满足 \(-1\)。 FLT 应用：求 \(7^{62}\pmod{11}\)。\(11\) 素数，\(7^{10}\equiv1\pmod{11}\)，故 \(7^{62}=7^2\cdot(7^{10})^6\equiv7^2\cdot1\equiv49\equiv5\pmod{11}\)。 模方程：\(5x+4y\equiv0\pmod7,\;2x+y\equiv4\pmod7\)。一式减 4 倍二式：\(5x+4y-8x-4y\equiv0-16\pmod7\implies -3x\equiv-2\pmod7\)，\(3x\equiv2\pmod7\)，\(3^{-1}\equiv5\pmod7\)，\(x\equiv3\pmod7\)，代回得 \(y\equiv5\pmod7\)。
两者相互独立。欧拉回路要求每条边恰好一次，Hamiltonian 回路要求每个顶点恰好一次。\(Q_3\) 有 Hamiltonian 回路但无欧拉回路（度 3 奇）；8字形图（两个三角形共顶点）有欧拉回路但无 Hamiltonian 回路。
握手定理 \(\sum\deg(v)=2|E|\) 对任意无向图成立，无论是否连通。每条边贡献 2 度，计数与连通性无关。奇度顶点个数为偶这一推论同样对任意图成立。
只是必要条件，非充分。\(K_{3,3}\) 满足 \(9\le 12\) 但非平面（含 \(K_{3,3}\) 细分）。必须用 Kuratowski 定理（不含 \(K_5/K_{3,3}\) 细分）或算法判定。
一般图需 \(d\) 或 \(d+1\) 色（Vizing 定理），奇环 \(C_{2k+1}\) 需 \(d+1=3\) 色。只有 Class 1 图（如树、偶环、完全图 \(K_{2n}\)）可 \(d\) 染色。
不成立。若 \(p\) 合数，必有素因子 \(q\le p-2\)，\((p-1)!\) 含 \(q\) 故 \(\equiv0\pmod q\)，不可能 \(\equiv-1\pmod p\)（否则模 \(q\) 也 \(-1\)，矛盾）。Wilson 是素数的充要判据，但计算阶乘太慢，不用于实际素性测试。
问题：设无向图 \(G\) 连通，恰好有 4 个奇度顶点。下列哪项正确？
问题：关于二分图，下列哪项是错误的？
问题：设图 \(G\) 的最大度为 \(d\)。下列关于边染色的命题哪个正确？
问题：Wilson 定理是素数的充要判据，为何不用于实际素性测试？
discussion/dis02a.pdf · 1 · confidence: high · Is there an Eulerian tour... condition that there is an Eulerian walk in an undirected graphdiscussion/dis02a.pdf · 2-4 · confidence: high · Claim: ... The number of vertices of G that have odd degree is even. Prove using (i) Direct proof ... (ii) Induction on m = |E| (iii) Induction on n = |V|discussion/dis02b.pdf · 2-3 · confidence: high · Show that the edges of an n-dimensional hypercube can be colored using n colors ... Show that for any n ≥ 1, the n-dimensional hypercube is bipartitehomework/hw03.pdf · 1 · confidence: high · Prove that for any graph with at least 15 vertices, G being planar implies that G is non-planar. Construct a counterexample to show that the converse does not hold.homework/hw03.pdf · 1-2 · confidence: high · Show that a hypercube has an Eulerian tour if and only if n is even. Show that every hypercube has a Hamiltonian tour.homework/hw03.pdf · 2-3 · confidence: high · Prove that any graph with maximum degree d ≥ 1 can be edge colored with 2d − 1 colors. Show that a tree can be edge colored with d colorshomework/hw03.pdf · 3 · confidence: high · Solve the following modular arithmetic equations... Wilson's Theorem... if and only if p is prime: (p − 1)! ≡ −1 (mod p)cs70-cheatsheet.pdf · Note 5–6 · confidence: medium · Eulerian tour iff connected even degree; Handshaking total degree 2|E|; planar e ≤ 3v-6; Wilson (p-1)! ≡ -1 mod p; FLT a^{p-1} ≡ 1 mod p