答 案
见解析
解析
证明：最多只有
个人，
否则考虑某一点引出的六条同色边所在的子图，
必然有同色三角形，和拉姆塞定理矛盾．
对于朋友，敌人，陌生人，分别用三种颜色连边
．对于点
，
，
，
代表三种相连边的数量．
有
，
，
．
同一点引出的两条颜色不同的边称为一对好边，
共有
组好边．
．
．
，
有
．
类似的，有
．
所以
．
也就是
，最大为
．
答 案
见解析
解析
解：设图
有
个顶点，是
的一个顶点．
若
．取
个与
相邻的顶点
，
，
，
，
．
将
中其余的顶点以及关联的边去掉得
，
根据
的定义，
中含有
或
中含有
．
如果
含有
，
那么在
中，
与这个
组成完全图
．
如果
中含有
，
则
中也含有这个
．
若与
相邻的顶点数
，
则
至少与
个顶点不相邻．
设与
不相邻的顶点为
，
，
，
，
，
模块
模块1：
1
1
例题1
16
Ai
xi
y
i
z
i
xi
y
i
z
⩽
i
5
S = 2C
n
3
S =
x
y
+ y
z
+ x
z
∑
i
i
i
i
i
i
x
+
i
y
+
i
z
=
i
n −1
f x, y, z =
(
)
xy + yz + zx
f x, y, z −
(
)
f 5, x + y −5, z =
(
)
x −5
y −5 ⩾
(
) (
)
0
f 5, x + y −5, z −
(
)
f 5, 5, x + y + z −10 ⩾
(
)
0
S ⩾nf 5, 5, n −11 =
(
)
n 10n −85
(
)
2C
⩾
n
3
n 10n −85
(
)
n
12
例题2
G
r p, q −1 +
(
)
r p −1, q
(
)
G
d v
⩾
( 1)
r p −1, q
(
)
δ = r p −1, q
(
)
v
1
v
2
v
3
⋯
v
δ
v
δ+1
G
G1
δ −r p −1, q
(
)
G
1
K
p−1
G1
K
p
G1
K
p−1
G
v
1
K
p−1
Kp
G1
K
q
G
K
q
v
1
< r p −1, q
(
)
v
1
r p, q −1
(
)
v
1
v
2
v
3
⋯
v
δ
v
δ+1
其中
．
将
中除
，
，
，
外的顶点以及关联的边去掉得图
．
根据
的定义，
中含有
或
中含有
．
如果
中含有
，
则
中也含有这个
．
如果
中含有
，
则
中，
与这个
组成
．
综合起来便得
．
如果
与
都是偶数．
取有
个顶点的图
．
因奇顶点的个数是偶数，
而
是奇数．
因而
中必有一个偶顶点
，
对于
，或者
或者
少与
个顶点不相邻．
因与
相邻的顶点数为偶数，
故在前一种情况，
，
照上面完全同样的证法得出
．
答 案
见解析
解析
证明：记
，我们对进行归纳．
当
时，
．左边是
，右边是
，命题成立．
设当
时，命题成立．
当
时，在
，
或
，
的情况下，
．
命题仍成立．
当
，
，
的情况下，
．
．
命题仍成立．
根据数学归纳法，定理四得证．
答 案
见解析
1
1
ε = r p, q −1
(
)
G
v
2
v
3
⋯
v
δ+1
G
2
ε = r p, q −1
(
)
G
2
K
p
G2
K
q−1
G2
K
p
G
K
p
G2
K
q−1
G
v
1
K
q−1
Kq
r p, q ⩽
(
)
r p, q −1 +
(
)
r p −1, q
(
)
r p, q −1
(
)
r p −1, q
(
)
r p, q −1 +
(
)
r p −1, q −
(
)
1
G
r p, q −1 +
(
)
r p −1, q −
(
)
1
G
v
1
v
1
d v
⩾
( 1)
r p −1, q −
(
)
1
v
1
r p, q −1
(
)
v
1
d v
⩾
( 1)
r p −1, q
(
)
r p, q ⩽
(
)
r p, q −1 +
(
)
r p −1, q −
(
)
1
< r p, q −1 +
(
)
r p −1, q
(
)
例题3
l = p + q
l
l = 4
p = q = 2
r 2, 2 =
(
)
2
C
=
4−2
1
2
l = k k ⩾4
(
)
l = k + 1
p = k −1
q = 2
p = 2
q = k −1
r k −1, 2 =
(
)
r 2, k −1 =
(
)
k −1 = C
=
k−1
k−2
C
k−1
1
p ⩾3
q ⩾3
p + q = k + 1
r p, q ⩽
(
)
r p, q −1 +
(
)
r p −1, q
(
)
r p, q ⩽
(
)
r p −1, q +
(
)
r p, q −1
(
)
⩽C
+
p+q−3
p−2
C
p+q−3
p−1
= C
p+q−2
p−1
例题4
解析
证明：在每个面中取一点
，
如果两个面有公共边，
则在所取的两个点之间连一条边，
这样得到的图
称为
的对偶图．
在
中，从一个面穿过某条边
到另一个面，
就相当于在
中从一个顶点沿一条边到另一个顶点．
因此，若
中有满足条件
、
的折线存在，
那么
就是一条链(
，
不在同一面内)或一个圈(
，
在同一面内)，
即
可以一笔画成．
但
的个顶点全是奇顶点，
至少需两笔才能画成．
答 案
见解析
解析
解：所给的图有
个奇顶点
，
．
如果要使它是一个圈，
至少要加条边．如图所添加的条边
后，
能使得该图是一个圈，
图中所示的圈使得路径最短．
1
1
v
j = 1, 2, 3, 4
j
′ (
)
G∗
G
G
ei
G∗
G
1
( )
2
( )
μ
G∗
Q
1
Q
2
Q
1
Q
2
G∗
G∗
4
例题5
16
B
i
C
i = 1, 2, ⋯, 8
i (
)
8
8
B
C
i = 1, 2, ⋯, 8
i
i (
)
例题6
答 案
见解析
解析
证明：先证明
是连通图．
若
有两个或两个以上的连通部分，
设其中之一有
个顶点，另一部分有
个顶点．
分别从中各取一顶点
、
，
则
，
．
故
，
这与题设矛盾，
所以
是连通图．
现证明存在哈密顿链．证明的方法实际上给出一种哈密顿链的构造步骤．
设在
中有一条从
到
的链：
．
如果有
或
与不在这条链上的一个顶点相邻，我们可扩展这条链，使它包含这个顶点．
否则
和
都只与这条链上的顶点相邻，
这时存在一个圈包含顶点动，
，
，
，
．
假设与
点相邻的顶点集是
，
这里
，
，
，
都是链
中的点，且
．
如果
与
相邻，则显然存在一个圈
．
如果
和
不相邻，
则必然存在一点
和
相邻，
而
和
相邻，
如图
所示．
因为否则
最多只和
个顶点相邻，
即排除
，
，
，
和
自身，
这样
，
这与假设矛盾．
因而存在
，
，
，
，的圈
．
若
，实际上已存在一个哈密顿圈．
若
，
因为
是连通的，
所以在
中必有一个不属于这个圈的顶点
与
中的某一顶点
相邻，
如图
所示．
于是就得到一个包含
，
，
，
，
的圈：
．
不断重复上面的步骤直到存在一条具有
条边的链为止．
G
G
n1
n2
v
1
v
2
d v
⩽
( 1)
n
−
1
1
d v
⩽
( 2)
n
−
2
1
d v
+
( 1)
d v
⩽
( 2)
n
+
1
n
−
2
2 < n −1
G
G
v
1
v
p
v
v
⋯v
1
2
p
v
1
v
p
v
1
v
p
v
1
v
2
⋯
v
p
v
1
v
, v
, ⋯, v
{ j
1
j
2
j
k }
v
j
1
v
j
2
⋯
v
j
k
v
v
⋯v
1
2
p
p < n
v
1
v
p
v
v
⋯v
v
1
2
p
1
v
1
v
p
v
2 ⩽l ⩽p
1 (
)
v
1
v
l−1
v
p
6 −8
v
p
p −k −1
v
j
−1
1
v
j
−1
2
⋯
v
j
−1
k
v
p
d v
+
( 1)
d v
⩽
( p)
k + p −k −1 =
(
)
p −1 < n −1
v
1
v
2
⋯
v
p
v
v v
⋯v
v
v
⋯v
v
1
l
l+1
p
l−1
l−2
2
1
p = n
p < n
G
G
v′
v
v
⋯v
1
2
p
v
k
6 −9
v
1
v
2
⋯
v
p
v′
v v
v
⋯v
v
v
⋯v
v
v
⋯v
v
′ k
k+1
l−1
p
p−1
l
1
2
k
′
n −1
例题7
答 案
见解析
解析
证明：当
时，由所给条件知
一定是完全图
，
命题成立．
设
，用反证法证明．
设
是有个顶点且满足度数条件却没有哈密顿圈的图．
不妨设
是具有这种性质的边数最大的图，
也就是说
添上一条边就具有哈密顿圈(否则
可以添加一些边，直到不能再添为止，加边后顶点的
度数条件仍满足)，
由此得出在图
中有一条包含图中每一个顶点的哈密顿链，
记为
．
则
与
不相邻，
于是
．
那么在
，
，
，
中必有一点
，使
与
相邻，
与
相邻，
如图
所示．否则，
有
个点
，
，
，
与
相邻，
而
与
，
，
，
都不相邻，
从而
，
则
，
这与条件矛盾．故
存在一条哈密顿圈
．
这又与假设矛盾．
从而命题得证．
答 案
见解析
解析
证明：用个点表示个人，作完全图
，
则
中的一个哈密顿圈就是一次晚餐的就座方法．
可见，晚餐最多能进行的次数就是
中无公共边的哈密顿圈的个数．
中有
条边，每个哈密顿圈有条边，
因此，边不相重的哈密顿圈最多有
个．
当
时，将顶点，，，
，
排列如图．
先取一个哈密顿圈
，
然后绕点依次顺时针旋转
，
，
，
，
共产生
个无公共边的哈密顿圈，
如果
，
那么每次在中间添加一个顶点，
1
1
n = 3
G
K
3
n ⩾4
G
n
G
G
G
G
v
v
⋯v
1
2
n
v
1
v
n
d v
+
( 1)
d v
⩾
( 2)
n
v
2
v
3
⋯
v
n−1
v
i
v
1
v
i
v
n
v
i−1
6 −11
d v
=
( 1)
k
v
i
1
v
i
2
⋯
v
2 ⩽i
⩽i
⩽⋯⩽i
⩽n −1
i
k (
1
2
k
)
v
1
v
n
v
i
−1
1
v
i
−1
2
⋯
v
i
−1
k
d v
⩽
( n)
n −1 −k
d v
+
( 1)
d v
⩽
( n)
k + n −1 −k = n −1 < n
G
v
v
⋯v
v
v
⋯v
v
1
2
i−1
n
n−1
i
1
例题8
n
n
K
n
K
n
K
n
K
n
n n −1
2
1
(
)
n
[
2
n −1 ]
n = 2k + 1
0
1
2
⋯
2k
0, 1, 2, 2k, 3, 2k −1, 4, ⋯, k + 3, k, k + 2, k + 1, 0
(
)
0
k
π
k
2π
⋯
k −1
(
) k
π
k = [
2
n −1 ]
n = 2k + 2
v
同样有个哈密顿圈．
答 案
见解析
解析
证明 ：设
与
平行，由于
与
之间和
与
之间顶点数相同，
所以
，
于是得到
和
平行的充要条件是
．
设
是一个哈密顿圈(
，
，
，
是，，
，
的一个排列)，
而其中任意的两条边在图中不是平行线．
因此
，
，
，
，
这
个数中的任意两个关于模
都不同余，
即上述这
个数是模
的一组完全剩余系．于是
．
另一方面，有
．
上面得出了两个矛盾的结果，从而命题得证．
答 案
见解析
解析
解：首先，每个点的度至少为，
不然存在一点
仅连出至多两边，
则把其中一边去掉后，剩下的
点必不在某个圈上，
1
1
k
例题9
A
A
i
j
A
A
k
l
A
i
A
l
A
j
A
k
i −l = k −j
A A
i
j
A A
k
l
i + j ≡k + l mod2n
(
)
A
A
⋯A
i
0
i
1
i
2n−1
i
0
i
1
⋯
i
2n−1
0
1
⋯
2n −1
i
+
0
i
1
i
+
1
i
2
i
+
2
i
3
⋯
i
+
2n−1
i
0
2n
2n
2n
2n
i
+ i
+
( 0
1)
i
+ i
+
( 1
2)
⋯+ i
+ i
( 2n−1
0)
≡0 + 1 + 2 + ⋯+ 2n −1 = 2n −
2
n
≡n mod2n
(
)
i
+ i
+
( 0
1)
i
+ i
+
( 1
2)
⋯+ i
+ i
( 2n−1
0)
= 2 i
+ i
+ i
+ ⋯+ i
( 0
1
2
2n−1)
= 2 0 + 1 + 2 + ⋯+ 2n −1
(
)
= 2n 2n −1
(
)
≡0 mod2n
(
)
例题10
3
A
A
这与条件不符．
因此
．
不难证得
，，．
若
，则去掉其中度数最大的点(显然该点度数至少为)，
得到一个长度为的圈．
由于与该点相邻的点在圈上必不相邻(否则将出现长度为的圈)，
于是被去掉的点至多能与圈上三个互不相邻的点相连，
因此该点度数至多为，
从而可知图中各点度数均恰为，
而
是奇数，
而实际上各点度数之和应为偶数，矛盾！
若
，则去掉度数最大的点后，得到一个长度为的圈．
被去掉的点至多能与圈上三个互不相邻的点相连，
因此它的度数至多为．
由此可知各点度数均为．
如图
，
，
，
，
的度数已经为，不能再连出任何边．
而
，
，
，
每点还要各连出一条边．
若
与
相连，
则
与
相连(连有两条边)，不可能．
若
与
相连，
则
与
相连，
而此时图中存在长度为的圈，矛盾！
若
与
相连，
则
与
相连，
而此时图中也存在长度为的圈，矛盾！
若
，由于
不是偶数，
因此不可能每点都是度，
故至少有一点，度数至少为．
我们把度数最大的点去掉，得到一个长度为的圈，
因此被去掉的点至多能与圈上个互不相邻的点相连，
因此图中的点度数最大为，最小为．
如图
，
则点
至少要再连出一条边．
显然
不能与
，
再连边．
若
与
连边，
则图中存在长度为的圈，
同理
不能与
相连．
若
与
相连，
则图中也将存在长度为的圈，矛盾！
故
只可能与
或
连边．
由对称性可设
与
相连．仿上讨论可知
与
相连(若
与
相连，
则
的度数已达到，矛盾！)，
与
相连，
与
相连．
此时图中任何两点不可能再连边，
则去掉点
后，
图中应存在长度为的圈．
而事实上，
若图中存在长度为的圈，
则
，
，
，
，
，
必在圈上，
而该边已构成一个长度为的圈，矛盾！
n ⩾3
n=4
/
5
6
n = 7
3
6
7
3
3
3 × 7 = 21
n = 8
7
3
3
1
( )
A
C
F
O
3
B
D
E
G
B
G
D
E
B
D
E
G
8
B
E
D
G
8
n = 9
3 × 9 = 27
3
4
8
4
4
3
2
( )
B
B
A
C
B
D
9
B
H
B
F
9
B
E
G
B
E
H
C
H
E
E
5
F
A
D
G
A
8
8
BE
BC
HG
HC
FE
FG
6
6
由以上讨论可知，满足要求的值至少为
．
的例子如图
，称
图．
n
10
n = 10
3
( )
Peterson
