返回：0100 离散数学课程总目录 · 上一章：0105 等势、基数、序数与集合论公理 · 下一章：0107 欧拉图与哈密顿图

1、资料来源与学习目标

本章对应北大离散数学刘田老师“集合论与图论”第六章。Auto_Tutor 中整理到的资料包括：

资料 内容
6.1 图的基本概念 图、无向图、有向图、简单图、度、握手定理、度数列、Havel 定理、图同构、子图、补图
6.2 通路与回路 通路、简单通路、初级通路、回路、圈、周长、围长、扩大路径法
6.3 无向图的连通性 连通关系、连通分支、距离、直径、二部图、强/单向/弱连通
6.4 无向图的连通度 点割集、边割集、割点、桥、点连通度、边连通度、Whitney 不等式、Menger 定理、块
006 习题与答案 习题 1、2、3、5、11、14、16、18、22、25，重点考察握手定理、补图、自补图、极大路径法、连通度和块

本章的核心目标：把图论的对象语言搭起来。先会数点、数边、数度，再会判断“走法”和“连通性”，后面的欧拉图、哈密顿图、树、平面图都会反复调用这些定义。

2、颜色标注

颜色 含义
粉色 必背、必会证明、后续章节反复使用
蓝色 核心术语和定义
橙色 易错点、边界条件
绿色 理解提示和后续连接

3、章节主线

模块 本章要会什么 后续连接
图的定义 会区分无向图、有向图、多重图、简单图 所有图论章节
度与握手定理 会用 sum d(v)=2m 和奇度顶点偶数性 欧拉图、树
度数列 会判断可图化、可简单图化 构造图与反例
图同构与图族 会识别同构不变量、完全图、二部图、补图 自补图、平面图
通路与回路 会区分 walk、trail、path、cycle 欧拉/哈密顿
连通性 会找连通分支、距离、二部图判定 树、网络连通
连通度 会用割点、桥、点/边连通度衡量可靠性 Menger、块

4、图的基本概念

4.1 无向图与有向图

无向图：

1
2
3
G=<V,E>
V≠∅
E 是 V 中顶点形成的无序对的多重集

有向图：

1
2
3
D=<V,E>
V≠∅
E 是 V×V 中有序对的多重集

常见术语：

概念 含义
n 阶图 顶点数为 n 的图
有限图 顶点数、边数有限的图
零图 N_n 边集为空的 n 阶图
平凡图 N_1
空图 V=E=∅，有些教材允许单独讨论
底图/基图 有向图去掉方向后得到的无向图

本课件里一般把“图”默认成顶点集非空的图；但又会单独提“空图”。遇到定理时要看清条件是不是要求连通、简单、非平凡。

4.2 相邻、关联、环和平行边

概念 含义
顶点相邻 两个顶点之间有边相连
边相邻 两条边有公共端点
关联 顶点是某条边的端点
环 只与一个顶点关联的边，如 (v,v)
孤立点 不与任何边关联的顶点
平行边 端点相同的多条边；有向图要求起点终点都相同

简单图：

1
既无环，也无平行边的图。

对 n 阶无向简单图：

1
0 ≤ d(v) ≤ n-1

4.3 邻域与度

无向图中，顶点 v 的邻域：

1
N_G(v)={u∈V(G) | (u,v)∈E(G) 且 u≠v}

闭邻域：

1
N_G[v]=N_G(v)∪{v}

顶点的度：

1
d_G(v)=与 v 关联的边的次数之和

环对无向图顶点的度贡献为 2。这是用握手定理时最容易漏掉的地方。

有向图中：

1
2
3
d_D^+(v)=v 的出度
d_D^-(v)=v 的入度
d_D(v)=d_D^+(v)+d_D^-(v)

最大度与最小度：

1
2
Δ(G)=max{d_G(v)}
δ(G)=min{d_G(v)}

有向图还可定义最大/最小出度、最大/最小入度：

1
Δ^+(D), δ^+(D), Δ^-(D), δ^-(D)

5、握手定理与度数列

5.1 无向图握手定理

设无向图 G=<V,E>，顶点为 v_1,v_2,...,v_n，边数为 m，则：

1
d(v_1)+d(v_2)+...+d(v_n)=2m

推论：

1
任何图中，奇度顶点的个数是偶数。

握手定理就是“每条边伸出两只手”。普通边给两个端点各贡献 1，环给同一个端点贡献 2，总贡献始终是 2m。

5.2 有向图握手定理

设有向图 D=<V,E>，边数为 m，则：

1
2
3
sum d^+(v)=m
sum d^-(v)=m
sum d(v)=2m

5.3 度数列、可图化与可简单图化

度数列：

1
d=(d(v_1),d(v_2),...,d(v_n))

可图化：

1
存在某个图 G，使 d 是 G 的度数列。

非负整数列 d=(d_1,d_2,...,d_n) 可图化的充要条件：

1
d_1+d_2+...+d_n 是偶数

原因：

  1. 必要性来自握手定理。
  2. 充分性可以把奇数度顶点两两连边，剩下偶数度用环补齐。

可简单图化：

1
存在某个无向简单图 G，使 d 是 G 的度数列。

对无向简单图，至少要满足：

1
2
n-1 ≥ d_1 ≥ d_2 ≥ ... ≥ d_n ≥ 0
d_1+d_2+...+d_n 是偶数

Havel 定理：

1
2
3
4
5
6
d=(d_1,d_2,...,d_n), n-1≥d_1≥d_2≥...≥d_n≥0

d 可简单图化
⇔
d'=(d_2-1,d_3-1,...,d_{d_1+1}-1,d_{d_1+2},...,d_n)
可简单图化

操作直觉：

1
2
取最大度 d_1 的顶点，把它连向后面 d_1 个最大度顶点；
然后删掉这个顶点，后面这些顶点的需求度各减 1。

Havel 化简每一步都要重新按非增顺序排序；一旦出现负数，或某个数超过剩余顶点数减一，就不可简单图化。

6、图同构、图族与图运算

6.1 图同构

无向图 G_1=<V_1,E_1> 与 G_2=<V_2,E_2> 同构，记作 G_1≅G_2，若存在双射：

1
f:V_1→V_2

满足：

1
(u,v)∈E_1 ⇔ (f(u),f(v))∈E_2

有向图同构类似，只是要保持有向边：

1
<u,v>∈E_1 ⇔ <f(u),f(v)>∈E_2

同构的图具有完全相同的图论性质，例如：

1
顶点数、边数、度数列、连通性、是否二部图、是否有圈、连通度等。

证明两个图不同构，常用“不变量”找矛盾；证明两个图同构，则必须给出顶点双射并检查邻接关系。

6.2 常见图族

图族 记号/说明
完全图 K_n，任意两个不同顶点相邻
零图 N_n，没有边
r 部图 顶点可分成 r 个互不相交部分，边只跨不同部分
二部图 G=<V_1,V_2;E>，也叫偶图
完全二部图 K_{r,s}
路径 P_n
圈 C_n
轮 W_n
超立方体 Q_n
竞赛图 任意两点之间恰有一条有向边

6.3 子图、导出子图与补图

子图：

1
G'⊆G ⇔ V(G')⊆V(G) 且 E(G')⊆E(G)

生成子图：

1
G'⊆G 且 V(G')=V(G)

顶点导出子图：

1
G[V_1]：保留 V_1 中顶点，以及 G 中两端都在 V_1 内的边

边导出子图：

1
G[E_1]：保留 E_1 中边，以及这些边关联到的顶点

补图：

1
\overline{G}=<V, E(K_n)-E(G)>

自补图：

1
G≅\overline{G}

6.4 图运算

运算 含义
G-e 删除边 e
G-v 删除顶点 v 以及它关联的边
G\e 收缩边 e=(u,v)，把 u,v 合并
G+(u,v) 加一条新边 (u,v)
G_1∪G_2 并图
G_1∩G_2 交图
G_1-G_2 差图
G_1⊕G_2 环和，保留只出现一次的边
G_1+G_2 联图，把两个不交图之间所有跨边都加上
G_1×G_2 积图

7、通路与回路

7.1 通路

通路 walk 是顶点和边的交替序列：

1
Γ=v_0 e_1 v_1 e_2 ... e_l v_l

其中每条边 e_r 都连接相邻的两个顶点。

概念 条件
起点 v_0
终点 v_l
通路长度 边的条数 l
回路 closed walk v_0=v_l
简单通路 没有重复边
简单回路 没有重复边的回路
初级通路/路径 没有重复顶点
初级回路/圈 除起终点相同外，没有重复顶点

这里的“简单通路”是不重复边，而“初级通路/路径”才是不重复顶点。很多英文教材会把 path 直接定义成不重复顶点，所以翻译时要看课程定义。

简单图中的通路或回路可以只写顶点序列；非简单图中如果有平行边，顶点序列可能无法唯一确定边。

7.2 周长与围长

对含圈的无向简单图：

1
2
c(G)=最长圈的长度，称为周长
g(G)=最短圈的长度，称为围长

典型例子：

1
2
3
4
c(K_n)=n, n≥3
g(K_n)=3, n≥3
c(K_{n,n})=2n
g(K_{n,n})=4, n≥2

7.3 通路压缩定理

定理 7.6：

1
2
在 n 阶图 G 中，若从不同顶点 u 到 v 有通路，
则从 u 到 v 有长度不超过 n-1 的路径。

证明思路：

1
2
3
若通路长度超过 n-1，则顶点数超过 n，必有重复顶点；
重复顶点之间形成回路，把这段回路删掉；
不断删除，直到没有重复顶点。

定理 7.7：

1
2
在 n 阶图 G 中，若从 u 到自身有回路，
则有从 u 到自身长度不超过 n 的圈。

7.4 扩大路径法

极大路径：

1
无向简单图中，路径的两个端点都不与路径之外的顶点相邻。

扩大路径法：

1
2
只要路径不是极大路径，就从某个端点继续向外扩展；
有限图中这个过程最终停在一条极大路径。

典型结论：

1
2
若 G 是 n≥3 阶无向简单图，且 δ(G)≥2，
则 G 中有长度至少 δ(G)+1 的圈。

证明抓手：

  1. 取一条极大路径 P=v_0v_1...v_k。
  2. 端点 v_0 的所有邻点都在路径上。
  3. 因为 d(v_0)≥δ(G)，存在足够远的邻点 v_i。
  4. v_0v_1...v_iv_0 构成长度至少 δ(G)+1 的圈。

8、连通性

8.1 无向图连通

在无向图 G=<V,E> 中定义：

1
u~v ⇔ u 与 v 之间有通路

规定 u~u。于是 ~ 是等价关系：

性质 原因
自反 规定 u~u
对称 无向通路可以反向走
传递 两段通路可以拼接

连通分支：

1
V/~ 的每个等价类诱导出的子图。

连通分支数：

1
p(G)=|V/~|

连通图：

1
p(G)=1

非连通图/分离图：

1
p(G)>1

8.2 距离与直径

短程线/测地线：

1
u,v 之间长度最短的通路。

距离：

1
d_G(u,v)=u,v 之间短程线的长度；若不可达，则为 ∞。

直径：

1
d(G)=max{d_G(u,v) | u,v∈V(G)}

典型例子：

1
2
3
4
d(K_n)=1, n≥2
d(C_n)=floor(n/2)
d(N_1)=0
d(N_n)=∞, n≥2

距离函数满足：

1
2
3
d(u,v)≥0，且 d(u,v)=0 ⇔ u=v
d(u,v)=d(v,u)
d(u,w)≤d(u,v)+d(v,w)

8.3 二部图判定

定理 7.8：

1
G 是二部图 ⇔ G 中无奇圈。

证明主线：

  1. 若 G 是二部图，圈必须在两个部分之间交替走，所以长度为偶数。
  2. 若 G 无奇圈，取一个基准点 v，按到 v 的距离奇偶性分成两类：
1
2
V_1={u | d(u,v) 为偶数}
V_2={u | d(u,v) 为奇数}

同一类内部不能有边，否则会构造出奇圈。

“二部图 ⇔ 无奇圈”是后面判定树、匹配、图着色时非常常用的结论。

8.4 连通图的边数下界

定理 7.9：

1
2
若无向图 G 连通，顶点数为 n，边数为 m，
则 m≥n-1。

直觉：

1
n 个顶点至少要用 n-1 条边才能连成一片。

等号情形会导向下一章附近的树：

1
连通且 m=n-1 的无向简单图是树。

8.5 有向图连通性

可达：

1
u→v ⇔ 从 u 到 v 有有向通路

双向可达：

1
u↔v ⇔ u→v 且 v→u

有向图连通性的三种强度：

概念 含义
弱连通 底图连通
单向连通 任意两点之间至少有一个方向可达
强连通 任意两点之间双向可达

强连通分支：

1
双向可达关系的等价类诱导出的极大强连通子图。

两个常用结论：

1
2
D 强连通 ⇔ D 中有回路过每个顶点至少一次。
D 单向连通 ⇔ D 中有通路过每个顶点至少一次。

9、点连通度与边连通度

9.1 点割集与割点

点割集：

1
2
3
∅≠V'⊂V(G)
p(G-V')>p(G)
且任意真子集 V''⊂V' 都不增加连通分支数。

割点：

1
v 是割点 ⇔ {v} 是点割集。

点连通度：

1
2
G 是无向连通非完全图时，
κ(G)=最小点割集的大小。

约定：

1
2
3
κ(K_n)=n-1
G 非连通时 κ(G)=0
κ(K_1)=0

9.2 边割集与桥

边割集：

1
2
3
∅≠E'⊂E(G)
p(G-E')>p(G)
且任意真子集 E''⊂E' 都不增加连通分支数。

边割集有一个重要性质：

1
若 E' 是边割集，则 p(G-E')=p(G)+1。

桥/割边：

1
e 是桥 ⇔ {e} 是边割集。

边连通度：

1
2
G 是无向连通图时，
λ(G)=最小边割集的大小。

约定：

1
G 非连通时 λ(G)=0

9.3 k 连通与 Whitney 不等式

k 连通：

1
κ(G)≥k

k 边连通：

1
λ(G)≥k

Whitney 不等式：

1
κ(G) ≤ λ(G) ≤ δ(G)

推论：

1
k 连通图一定是 k 边连通图。

反过来不一定成立：k 边连通并不保证 k 连通。边不容易断，不代表删点也不容易断。

9.4 Menger 定理与 2 连通判定

独立路径：

1
两条路径除起点和终点外没有其他公共顶点。

边不交路径：

1
两条路径没有公共边，但可以有公共顶点。

Menger 定理：

1
2
3
最小 x-y 割包含的顶点数
=
最大 x-y 独立路径条数。

2 连通的充要条件：

1
2
3
3 阶以上无向简单连通图 G 是 2-连通图
⇔ G 中任两顶点共圈
⇔ G 中任两顶点之间有 2 条以上独立路径。

2 边连通的充要条件：

1
2
3
3 阶以上无向图 G 是 2-边连通图
⇔ G 中任两顶点共简单回路
⇔ G 中任两顶点之间有 2 条以上边不交路径。

k 连通的充要条件：

1
2
3 阶以上无向图 G 是 k-连通图
⇔ G 中任两顶点之间有 k 条以上独立路径。

k 边连通的充要条件：

1
2
3 阶以上无向图 G 是 k-边连通图
⇔ G 中任两顶点之间有 k 条以上边不交路径。

9.5 割点、桥与块

割点判定：

1
2
3
无向连通图 G 中顶点 v 是割点
⇔
存在 u,w≠v，使得从 u 到 w 的每条路径都经过 v。

桥判定：

1
2
3
4
5
无向连通图 G 中边 e 是桥
⇔
G 的任何圈都不经过 e
⇔
删去 e 后图的连通分支数增加。

块：

1
极大无割点连通子图。

几个概念的关系：

概念 判断
2 连通图 连通且无割点，且点连通度至少为 2
2 边连通图 连通且无桥，且边连通度至少为 2
块 极大无割点连通子图
K_2 是块，但不是 2 连通图，也不是 2 边连通图

10、习题与答案

习题 1：用握手定理求最少顶点数

题目：设无向图 G 有 16 条边，有 3 个 4 度顶点、4 个 3 度顶点，其余顶点的度数均小于 3，问 G 中至少有几个顶点？

答案：至少 11 个顶点。

设 G 至少有 n 个顶点，则除已知的 7 个顶点外，其余 n-7 个顶点度数至多为 2。由握手定理：

1
2m=32 ≤ 3×4+4×3+2(n-7)

所以：

1
2
32 ≤ 12+12+2n-14 = 2n+10
n ≥ 11

当其余 4 个顶点都是 2 度顶点时达到下界，因此至少有 11 个顶点。

习题 2：9 阶图中 5 度点与 6 度点数量

题目：设 9 阶无向图 G 中，每个顶点的度数不是 5 就是 6，证明 G 中至少有 5 个 6 度顶点或至少 6 个 5 度顶点。

证明：反证。若不是这样，则：

1
2
6 度顶点至多 4 个
5 度顶点至多 5 个

但奇度顶点个数必须为偶数，因此 5 度顶点不可能恰好有 5 个，只能至多 4 个。于是顶点总数至多：

1
4+4=8

这与 G 是 9 阶图矛盾。

习题 3：不存在奇数个奇边面多面体

题目：证明空间中不可能存在有奇数个面且每个面均有奇数条棱的多面体。

证明：构造一个图 G=<V,E>：

1
2
V={多面体的面}
两个面有公共棱时，在对应顶点之间连边

若存在这样的多面体，则：

1
2
顶点数 |V| 为奇数；
每个顶点的度数都是奇数。

于是 G 中奇度顶点个数为奇数，违反握手定理推论“奇度顶点个数必为偶数”。故不存在。

习题 5：满足 2n-3=m 的 3 正则图

题目：设 n 阶无向简单图 G 为 3 次图，即 3-正则图，边数 m 与 n 满足：

1
2n-3=m

试问 G 有几种非同构情况？并证明结论。

答案：有 2 种非同构情况。

由 3 正则和握手定理：

1
3n=2m

又有：

1
m=2n-3

联立：

1
2
3
4
3n=2(2n-3)
3n=4n-6
n=6
m=9

所以 G 是 6 阶 9 条边的 3 正则简单图。

考虑补图。K_6 有：

1
C(6,2)=15

条边，所以补图有：

1
15-9=6

条边。原图 3 正则，则补图每个顶点度数为：

1
5-3=2

即补图是 6 阶 6 条边的 2 正则简单图。

2 正则简单图的每个连通分支都是圈。6 个顶点只能分成：

1
2
C_6
C_3∪C_3

两种非同构情况。因此原图也只有两种非同构情况，它们分别是上述两种补图的补图。

习题 11：自补图的阶数形式

题目：设无向图 G 是 n 阶自补图，证明：

1
n=4k 或 n=4k+1

其中 k 为正整数。

证明：G 自补，说明：

1
G≅\overline{G}

所以 G 与补图边数相同。设 G 的边数为 m，则：

1
2m = C(n,2)=n(n-1)/2

即：

1
4m=n(n-1)

由于 n 与 n-1 互素，要让乘积被 4 整除，只能有：

1
2
3
n≡0 (mod 4)
或
n≡1 (mod 4)

所以：

1
n=4k 或 n=4k+1

习题 14：连通非完全图中存在长度为 2 的非闭三角

题目：设 n≥3 阶无向简单图 G 是连通的，但不是完全图。证明存在 u,v,w∈V(G)，使得：

1
2
(u,v),(v,w)∈E(G)
而 (u,w)∉E(G)

证明：反证。假设对任意 u,v,w∈V(G)，只要：

1
(u,v),(v,w)∈E(G)

就有：

1
(u,w)∈E(G)

任取两个不同顶点 u,w。由连通性，存在从 u 到 w 的通路：

1
P=u v_1 v_2 ... v_r w

若通路长度为 1，则 u,w 已相邻。若通路长度大于 1，由假设可把连续两条边“缩短”为一条边：

1
(u,v_1),(v_1,v_2)∈E(G) ⇒ (u,v_2)∈E(G)

继续归纳，最终得到：

1
(u,w)∈E(G)

因此任意两个不同顶点都相邻，G 是完全图，矛盾。故结论成立。

习题 16：圈长最大公约数只能是 1 或 2

题目：设 G 是无向简单图，δ(G)≥3，证明 G 中各圈长度的最大公约数为 1 或 2。

证明：不妨在某个连通分支中讨论。取一条极大路径：

1
P=v_0v_1...v_l

因为 P 极大，端点 v_0 不与路径外顶点相邻。又因为 δ(G)≥3，除 v_1 外，v_0 至少还与路径上两个顶点相邻。设：

1
v_0 与 v_r、v_s 相邻，其中 1<r<s≤l

于是得到三个圈：

1
2
3
C_1=v_0v_1...v_rv_0，长度 r+1
C_2=v_0v_1...v_s v_0，长度 s+1
C_3=v_0v_rv_{r+1}...v_s v_0，长度 s-r+2

设所有圈长的最大公约数为 k。那么 k 整除这三个圈长：

1
2
3
k | (r+1)
k | (s+1)
k | (s-r+2)

由前两式可得：

1
k | (s-r)

再结合第三式：

1
k | [(s-r+2)-(s-r)] = 2

所以：

1
k=1 或 k=2

习题 18：最小度推出连通与 k 连通

题目：设 G 是 n 阶无向简单图，证明：

1
2
(1) 当 δ(G)≥n/2 时，G 为连通图；
(2) 当 δ(G)≥(n+k-1)/2 时，G 为 k-连通图。

证明 (1)：反证。若 G 不连通，则至少有两个连通分支。取顶点数较少的连通分支 G_1，设：

1
|V(G_1)|=n_1≤floor(n/2)

任取 v∈V(G_1)，它只能与 G_1 内的顶点相邻，所以：

1
d_G(v)≤n_1-1≤floor(n/2)-1<n/2

这与 δ(G)≥n/2 矛盾。因此 G 连通。

证明 (2)：要证 G 是 k 连通，只需证明删除任意 k-1 个顶点后仍连通。

任取：

1
V'⊆V(G), |V'|=k-1

令：

1
2
G'=G-V'
n'=n-(k-1)=n-k+1

删除 k-1 个顶点后，任一剩余顶点的度最多减少 k-1，所以：

1
2
3
4
δ(G') ≥ δ(G)-(k-1)
      ≥ (n+k-1)/2-(k-1)
      = (n-k+1)/2
      = n'/2

由 (1) 可知 G' 连通。因此删除任意 k-1 个顶点后图仍连通，G 是 k 连通图。

习题 22：无偶圈图的块

题目：设 n≥2 阶无向简单连通图 G 中不含偶圈，证明 G 的块或为 K_2，或为奇圈。

证明：设 B 是 G 的任意一个块。

若 B 只有两个顶点，则由于 B 连通且极大无割点，它就是 K_2。

若 B 至少有三个顶点，则块没有割点，可视为 2 连通结构。由 2 连通图的性质，B 中任意两点共圈，因此 B 中存在圈。由于 G 中不含偶圈，B 中的圈都只能是奇圈。

下面证明 B 不能比某个奇圈多出额外的边或顶点。设 C 是 B 中一个奇圈。若 B 中还存在不完全属于 C 的路径 P，其两个端点 x,y 在 C 上，内部顶点或边在 C 外，则 C 上从 x 到 y 有两段弧。因为 C 是奇圈，这两段弧长度一奇一偶。

把 P 分别与这两段弧合起来，会得到两个圈；这两个圈的长度奇偶性相反，所以其中必有一个偶圈。这与 G 中不含偶圈矛盾。

因此 B 不能在奇圈外再有额外路径、额外边或额外顶点，只能是这个奇圈本身。故 G 的块或为 K_2，或为奇圈。

习题 25：传递竞赛图不可能强连通

题目：设 D 为竞赛图。若：

1
<u,v>, <v,w>∈E(D) ⇒ <u,w>∈E(D)

则称 D 为传递的竞赛图。证明 n≥2 阶传递竞赛图不可能是强连通的。

证明：传递竞赛图不含有向圈。反证，若存在有向圈：

1
v_1→v_2→...→v_r→v_1

由传递性，沿着：

1
v_1→v_2→...→v_r

可推出：

1
v_1→v_r

但有向圈又给出：

1
v_r→v_1

这与竞赛图中任意两点之间恰有一个方向的边矛盾。

若 D 强连通，任取两个不同顶点 u,v，有从 u 到 v 的通路，也有从 v 到 u 的通路。二者拼接得到一个有向闭通路，而闭通路中必含有有向圈。与上面“传递竞赛图不含有向圈”矛盾。

所以 n≥2 阶传递竞赛图不可能强连通。

11、复盘清单

  1. 无向图握手定理：sum d(v)=2m。
  2. 奇度顶点个数一定是偶数。
  3. 有向图中：总出度等于总入度，都等于边数。
  4. 简单图中每个顶点度数不超过 n-1。
  5. Havel 定理判断可简单图化时，每一步都要排序、减一、检查负数。
  6. 图同构要保持邻接关系；不同构常用度数列、连通性、圈等不变量排除。
  7. 简单通路是不重复边；路径/初级通路是不重复顶点。
  8. 二部图等价于无奇圈。
  9. 连通图至少有 n-1 条边。
  10. κ(G)≤λ(G)≤δ(G)。
  11. 桥不在任何圈上；割点会卡住某两点之间的所有路径。
  12. 块是极大无割点连通子图，K_2 是一个特殊块。

12、下一步

第七章进入欧拉图与哈密顿图。复习第六章时，先把“度数统计”“通路/回路分类”“连通分支”“割点与桥”四组概念稳住，再看欧拉图时会轻松很多。