第10章习题答案
习题10
1.(1)图G 的度数列为2、2、3、3、4，则G 的边数是多少？
(2)3、3、2、3和5、2、3、1、4能成为图的度数列吗？为什么？
(3)图G 有12条边，度数为3的结点有6个，其余结点的度数均小于3，问图G 中至多有几个结点？为什么？
解 (1)设G 有m 条边，由握手定理得2m ＝∑∈V
v v d )(＝2＋2＋3＋3＋4＝14，所以G 的边数7条。
(2)由于这两个序列中有奇数个是奇数，由握手定理的推论知，它们都不能成为图的度数列。 (3) 由握手定理得∑∈V
v v d )(＝2m ＝24，度数为3的结点有6个占去18度，还有6度由其它结点占有，其
余结点的度数可为0、1、2，当均为2时所用结点数最少，所以应由3个结点占有这6度，即图G 中至多有9个结点。
2.若有n 个人，每个人恰有3个朋友，则n 必为偶数。
证明 设1v 、2v 、…、n v 表示任给的n 个人，以1v 、2v 、…、n v 为结点，当且仅当两人为朋友时其对应的结点之间连一条边，这样得到一个简单图G 。由握手定理知
∑=n
k k
v d 1)(＝3n 必为偶数，从而n 必为偶数。
3.判断下列各非负整数列哪些是可图化的？哪些是可简单图化的？ (1)(1，1，1，2，3)。 (2)(2，2，2，2，2)。 (3)(3，3，3，3)。 (4)(1，2，3，4，5)。 (5)(1，3，3，3)。
解 由于非负整数列d ＝(d 1，d 2，…，d n )是可图化的当且仅当∑=n
i i d 1≡0(mod 2)，所以(1)、(2)、(3)、
(5)能构成无向图的度数列。
(1)、(2)、(3)是可简单图化的。其对应的无向简单图如图所示。
(5)是不可简单图化的。若不然，存在无向图G 以为1，3，3，3度数列，不妨设G 中结点为1v 、2v 、3v 、4v ，
且d(1v )＝1，d(2v )＝d(3v )＝d(4v )＝3。而1v 只能与2v 、3v 、4v 之一相邻，设1v 与2v 相邻，于是d(3v )＝d(4v )＝3不成立，矛盾。
4.试证明图10-48中的两个无向图是不同构的。
证明 因为两图中都有4个3度结点，左图中每个3度结点均与2个2度结点邻接，而右图中每个3度结点均只与1个2度结点邻接，所以这两个无向图是不同构的。
5.在图同构意义下，试画出具有三个结点的所有简单有向图。
解 具有三个结点的所有非同构的简单有向图共16个，如图所示，其中(8)
(16)为其生成子图。
6.给定无向完全图G ＝
解 (1)G 的所有子图如图所示。 (2)图
(8)
(1)(3)(5)
(6)
(7)
(9)(10)
(13)
(14)
(8)(9)
(10)
(11)
(12)
(1)(2)(3)
(4)
(5)
(6)
(7)
(18)是G 的所有生成子图。
7.(1)试给出一个五个结点的自补图。 (2)是否有三个结点或六个结点的自补图。
(3)一个图是自补图，则其对应的完全图的边数必是偶数。 (4)一个自补图的结点数必是4k 或4k ＋1。
解 (1)五个结点的图G 与它的补图G 如图所示。对G 与G 建立双射：1
v 1v ，2
v 2v ，3
v 3v ，4
v 4v ，
5
v 5v 。显然这两个图保持相应点边之间的对应的关联关系，故G
G 。因此，G 是五个结点的自补图。
(3)设图G 是自补图，有m 条
边，G 对应的完全图的边数
为s ，则G 对应的补图G 的边数为s －m 。因为G G ，故边数相等，即有m ＝s －m ，s ＝2m ，因此G 对
应的完全图的边数s 为偶数。
(2)由(3)知，自补图对应的完全图的边数为偶数。n 个结点的完全图n K 的边数为2
1
n (n －1)，当n ＝3或
n ＝6时，n K 的边数为奇数，因此不存在三个结点或六个结点的自补图。
(4)设G 为n 阶自补图，则需2
1n (n －1)能被2整除，因此n 必为4k 或4k ＋1形式。
8.一个n (n ≥2)阶无向简单图G 中，n 为奇数，已知G 中有r 个奇数度结点，问G 的补图G 中有几个奇数度结点？
（1）（2)G
G
解 由G 的补图G 的定义可知，G ∪
G 为n K ，由于n 为奇数，所以n K 中各顶点的度数n －1为偶数。对于图G 的任意结点v ，应有v 也是G 的顶点，且)(v d G ＋)(v d G ＝)(v d n K ＝n －1，由于n －1为偶数，所以)(v d G 和)(v d G 奇偶性相同，因此若G 中有r 个奇数度结点，则G 中也有r 个奇数度结点。
9.画出4阶无向完全图K 4的所有非同构的生成子图，并指出自补图来。 解 下图中的11个图是K 4的全部的非同构的生成子图，其中(7)为自补图。
10.设图G 中有9个结点，每个结点的度不是5就是6。试证明G 中至少有5个6度结点或至少有6个5度结点。
证明 由握手定理的推论可知，G 中5度结点数只能是0、2、4、6、8五种情况（此时6度结点数分别为9、7、5、3、1）。以上五种情况都满足至少5个6度结点或至少6个5度结点的情况。
11.证明3度正则图必有偶数个结点。
证明 设G 为任一3度正则图，有n 个结点1v 、2v 、…、n v ，则所有结点度数之和
∑=n
i i
v d 1
)(＝3n 。若
n 为奇数，则3n 也为奇数，与握手定理矛盾。故n 为偶数。
12.设G 为至少有两个结点的简单图，证明：G 中至少有两个结点度数相同。
证明 若G 中孤立结点的个数大于2，结论显然成立。若G 中有1个孤立结点，则G 中至少有3个结点，因而不考虑孤立结点，就是说G 中每个结点的度数都大于等于1。又因为G 为简单图，所以每个结点的度数都小于等于n -1。因而G 中结点的度的取值只能是1，2，…，n -1这n 个数。由抽屉原理可知，取n -1个值的n 个结点的度至少有两个是相同的。
13.给定无向图G ＝
(3)长度分别是最小和最大的基本回路。 (4)长度分别是最小和最大的简单回路。
(5)从a到d的距离。
(6)
(G )、
(G )、(G )、
(G )分别是多少？
解 (1)从a 到d 的所有基本路共有10条：abd ，abcd ，abed ，abced ，abecd ，afed ，afecd ，afebd ，afebcd ，
afecbd 。
(2)从a 到d 的所有简单路共有14条：除（1）中的10条外还有abcebd ，abecbd ，afebced ，afecbed 。 (3)长度最小的基本回路共4个：bceb ，bdeb ，cdec ，bcdb 。长度最大的基本回路共1个：abdcefa 。 (4)长度最小的简单回路共4个：bceb ，bdeb ，cdec ，bcdb 。长度最大的简单回路2个：abcebdefa ，afebcedba 。 (5)从a 到d 的距离为2。 (6)
(G )＝2，(G )＝2，
(G )＝2，
(G )＝4。
14.给定有向图G ＝
解 (1)d +(a )＝2，d -(a )＝1，d +(b )＝1，d -(b )＝2，d +(c )＝1，d -(c )＝1，d +(d )＝2，d -(d )＝2，d +(e )＝1，d -(e )＝1。
(2)从a 到d 的基本路2条：ad ，abd 。从a 到d 的简单路5条：ad ，abd ，adcbd ，adead ，adeabd 。 (3)基本回路共3个abdea ，adea ，bdcb .简单回路共4个：abdea ，adea ，bdcb ，adcbdea 。 15.(1)若无向图G 中只有两个奇数度结点，则这两个结点一定是连通的。 (2)若有向图G 中只有两个奇数度结点，它们一个可达另一个结点或互相可达吗？
证明 (1)设无向图G 中只有两个奇数度结点u 和v 。从u 开始构造一条回路，即从u 出发经关联结点u 的边1e 到达结点1u ，若)(1u d 为偶数，则必可由1u 再经关联1u 的边2e 到达结点2u ，如此继续下去，每条边只取一次，直到另一个奇数度结点为止，由于图G 中只有两个奇数度结点，故该结点或是u 或是v 。如果是v ，那么从u 到v 的一条路就构造好了。如果仍是u ，该回路上每个结点都关联偶数条边，而)(u d 是奇数，所以至少还有一条边关联结点u 的边不在该回路上。继续从u 出发，沿着该边到达另一个结点 1u ，依次下去直到另一个奇数度结点停下。这样经过有限次后必可到达结点v ，这就是一条从u 到v 的路。
(2)若有向图G 中只有两个奇数度结点，它们一个可达另一个结点或互相可达不一定成立。下面有向图中，只有两个奇数度结点u 和v ，u 和v 之间都不可达。
16.若无向图G 是不连通的，证明G 的补图G 是连通的。
证明 设无向图G 是不连通的，其k 个连通分支为1G 、2G 、…、k G 。任取结点u 、v ∈G ，若u 和
u v
w
v 不在图G 的同一个连通分支中，则[u ，v ]不是图G 的边，因而[u ，v ]是图G 的边；若u 和v 在图
G 的同一个连通分支中，不妨设其在连通分支i G （1≤i ≤k ）中，在不同于i G 的另一连通分支上取一结
点w ，则[u ，w ]和[w ，v ]都不是图G 的边，，因而[u ，w ]和[w ，v ]都是G 的边。综上可知，不管那种情况，u 和v 都是可达的。由u 和v 的任意性可知，G 是连通的。
17.完成定理10.11的证明。
证明 充分性：若连通图G 中存在结点u 和w ，使得连接u 和w 的每条路都经过e ，则在子图G －{e }中u 和w 必不可达，故e 是G 的割边。
必要性：若e 是G 的割边，则G －{e }至少有两个连通分支G 1＝
必
通过e ，即u 和w 之间的任意路必经过e 。
18.完成定理10.16的证明。
证明 先证任一结点至少位于一个单向分图中。
任给一结点v ，若v 是孤立结点，则含v 的平凡图即为单向分图。若v 不是孤立结点，则必有一个结点u ，使得u 与v 有一弧e 与它们联结。此时若有单向分图>=<111,E V G ，|1V |≥3，使u ，v ∈1V ，且
e ∈1E ，那么结论成立；若不存在这样的1G ，则由u ，v 和e 就构成一个单向分图。因此，任何结点至
少位于一个单向分图中。
其次证明，任何一条弧至少位于一个单向分图中。
任给一弧e ，其关联的结点u 和v 。若存在一单向分图>=<111,E V G ，|1V |≥3，使u ，v ∈1V ，且e ∈1E ，那么结论成立。否则，u ，v 和e 就构成一个单向分图。综上可知，任一弧至少位于一个单向分图中。
19.完成定理10.17的证明。
证明 显然任一结点和任一弧都位于一个弱分图中。
假设有一结点v 位于两个不同的弱分图>=<111,E V G 和>=<222,E V G 中，即v ∈1V ∩2V 。由于略去弧的方向后，1V 中所有结点与v 可达，2V 中所有结点也与v 可达，故1V 与2V 中所有结点可达，这与
1G 和2G 为弱分图矛盾，故任一结点不可能包含于不同的弱分图中，即任一结点能且只能位于一个弱分图
中。
假设一弧e 位于两个不同的弱分图中，该弧e 所关联的两个结点也位于两个不同的弱分图中，这是不可能的，因此任一弧也只能位于一个弱分图中。
20.给出3个4阶有向简单图D 1、D 2、D 3，使得D 1为强连通图；D 2为单向连通图但不是强连通图；
D 3是弱连通图但不是单向连通图，当然更不是强连通图。
解
（a）（b）（c）
图中得（a）为强连通图；（b）为单向连通图但不是强连通图；（c）是弱连通图但不是单向连通图，
当然更不是强连通图。
21.一个有向图D是单向连通图，当且仅当它有一条经过每一个结点的路。
证明充分性。
给定有向图D＝
v1e2v2e…1-n v1-n e n v，这时V＝{1v，
1
v，…，1-n v，n v}，E＝{1e，2e，…，1-n e }E，边i e（1≤i≤n－1）以i v为起点，以1+i v为终点。任给2
两个结点
v、m v∈V，不妨设l＜m，则l v l e1+l v…1-m e m v就是从结点l v到m v的路，故D是单向连通的。
l
必要性。
对结点数v进行归纳。
当v＝1或2时，单向连通图显然有一条经过每一个结点的路。
设v＝k时，有一条经过每一个结点的路
v2v…p v，其中结点可能有重复，这条路的下标只表示该路
1
所经过结点的次序，显然k≤p。
当v＝k＋1时，取一结点u，在图中删去结点u，使D－{u}还是单向连通图。根据归纳假设，D－
{u}有一条经过每一个结点的路
v2v…p v。令i＝max{s|s v到u有路}，j＝min{s|u到s v有路}。假如j＞
1
i＋1，则必有t满足i＜t＜j。由于图D是单向连通的，t v与u之间必有路。如果该路是从t v到u，则与i ＝max{s|
v到u有路}矛盾。如果该路是从u到t v，则与j＝min{s|u到s v有路}矛盾。故而j＞i＋1不
s
可能，只能是j≤i＋1。当j＝i＋1时，有经过每个结点的路
v2v…i v…u…1+i v2+i v…p v。当j≤i时，
1
有经过每个结点的路
v2v…j v…i v…u…j v…i v1+i v…p v。
1
22.设e为图G＝
证明设e为图G的第个连通分支
G的一条边。
i
若e不是
G的割边，则i G－e仍然连通，因而G的连通分支数不变，即
i
(G)＝(G－e) （1）
若e是
G的割边，则i G－e有且仅有两个连通分支，因而G－e比G多一个支连通分支，即
i
(G)＋1＝(G－e) （2）
. 由（1）和（2）可得(G )≤(G －e )≤
(G )＋1。
23.设G 是n 阶无向简单图，有m 条边，p 个连通分支，证明n －p ≤m ≤(n －p )(n －p ＋1)/2。 证明 （1）首先证明n －p ≤m 。对边数m 做归纳法。m ＝0时，G 为零图，p ＝n ，n －p ＝0，此时结论显然成立。
设m ＜k （k ≥1）时结论成立，要证m ≥3时结论成立。在G 中找一个边割集，不妨设这个边割集中的边为1e ，2e ，…，l e （l ≥1），设G 1＝G －{1e ，2e ，…，l e }，则G 1的连通分支数为p ＋1，边数为
m 1＝m －l （l ≥1），由归纳假设得n －（p ＋1）≤m －l ＝m －1，于是n －p ≤m 。
（2）再证m ≤(n －p )(n －p ＋1)/2。为证明此不等式，不妨设G 的各连通分支都是完全图，因为在这种情况下边数最多。而在l －1个连通分支都是完全图的情况下，又以p －1个为1K （平面图），一个n －
p ＋1阶完全图1+-p n K 时边数最多，此时的边数为(n －p )(n －p ＋1)/2。为此只需证明下面事实：设i n K 和j
n K 是G 的两个连通分支（i n ≥j n ≥1）。用1+i n K 和1-j n K 分别代替i n K 和j n K ，所得图的结点数和连通分支数没变，但边数增加了。证明如下：
(
21i n (i n ＋1)＋21(j n －1)(j n －2))－(21i n (i n －1)＋2
1
j n (j n －1))＝i n －j n ＋1＞0 综上所述就证明了结论。
24.设G ＝
通的。
证明 必要性。设G 是强连通的，此时若从S 到V －S 没有有向边，则S 中的任一结点u 到V －S 中的任一结点v 均没有有向路，从而与G 是强连通的矛盾。所以从S 到V －S 至少有一条有向边。故G 是1边连通的。
充分性。设G 是1边连通的。任意u 、v ∈V ，{u }到V －{u }至少有一条边，设为uu 1，而{u ，u 1}到V －{u ，u 1}至少有一条边uu 2或u 1u 2。无论那种情况都有从u 到u 2的有向路。因G 中结点有限，所以通过如上递归地求解，一定有u 到v 的有向路。故G 是强连通的。
25.证明在n 个结点的连通图G 中，至少有n －1条边。
证明 不妨设G 是无向连通图（若G 为有向图，可略去边的方向讨论对应的无向图）。
设G 中结点为1v 、2v 、…、n v 。由连通性，必存在与1v 相邻的结点，不妨设它为2v （否则可重新编号），连接1v 和2v ，得边1e ，还是由连通性，在3v 、4v 、…、n v 中必存在与1v 或2v 相邻的结点，不妨设为
3v ，将其连接得边2e ，续行此法，n v 必与1v 、2v 、…、1-n v 中的某个结点相邻，得新边1-n e ，由此可见
G
中至少有n －1条边。
.
26.试给出|V |＝n ，|E |＝2
1(n －1)(n －2)的简单无向图G ＝
27.一个n 阶连通图G 最少有几个割点？最多有几个割点？
解 一个n 阶连通图G 为树时割点最少，只有一个；为完全图时割点最多，有n －1个。 28.求完全图K n 中任两点之间长为k 的路的数目。
解 设E 为元素全为1的n 阶矩阵，I 为阶单位矩阵，于是K n 的邻接矩阵为A ＝E －I 。K n 中长度为k 的路的数目由决定k A 。
由于k
A ＝(E －I )k
＝
∑
=--k
i i k
i
k C I E 0
)
(＝∑
=---+-k
i i
k i i k k
C n E
I 1
1)1()1(＝E n n
I k k k ])1()1[(1)1(---+-
所以，???
????
≠---=---+-=j i n n j i n n a k k k k k k ij
])1()1[(1])1()1[(1)1()
(。 29.有向图D 如图10-51所示： (1)求D 的邻接矩阵A 。
(2)D 中v 1到v 4长度为4的路有多少？ (3)D 中v 1到自身长度为3的回路有多少？ (4)D 中长度为4的路数为多少？其中有几条回路？ (5)D 中长度小于等于4的路有多少？其中有多少条回路？ (6)D 是哪类连通图？
解 (1) 求D 的邻接矩阵为：
??
?
?
?
?
?
?
?=0100100001000121
A
且有
???????
?
?=010000100100013
21
2A ???????
??=010********
034213A ???
?
??
?
?
?=10000100100
0462
14A (2)由4A 中4)
4(14
=a 可知，D 中v 1到v 4长度为4的路有4条，分别为：1e 1e 4e 6e 、4e 6e 7e 6e 、1e 2e 5e 6e 、1e 3e 5e 6e 。
.
(3)由3A 中1)
3(11
=a 可知，D 中v 1到自身长度为3的回路只有1条，为1e 1e 1e 。
(4)D 中长度为4的路总数为
16414
1
)4(=∑∑==i j ij
a
，其中对角元素之和为3，说明长度为4的回路为3条。
(5)D 中长度小于等于4的路总数为A 、2A 、3A 、4A 中全体元素之和：7＋10＋13＋16＝46，其中回路数为：1＋3＋1＋3＝8。
(6)由??
?
?
?
?
?
?
?=+++=220022002200
814844324A A A A B 可知，D 是单向连通图。
30.有向图G 如图10-52所示，试求： (1)求G 的邻接矩阵A 。
(2)求出A 2、A 3和A 4，v 1到v 4长度为1、2、3和4的路有多少？ (3)求出A T A 和AA T ，说明A T A 和AA T 中的第(2，2)元素和第(2，3)元素的意义。
(4)求出可达矩阵P 。 (5)求出强分图。
解 (1)求G 的邻接矩阵为：
??
?
?
?
?
?
?
?=0010101011001010
A
(2)由于
???????
?
?=1100111010201110
2
A ???
????
?
?=1020212
02210212
03A ???
?
??
?
?
?=221032303140323
04
A 所以v 1到v 4长度为1、2、3和4的路的个数分别为1、1、2、3。 (3)由于
???????
?
?=3120110021300000
A A T ???
?
??
?
?
?=12011212012
1121
2T AA 再由定理10.19可知，所以A T A 的第(2，2)元素为3，表明那些边以2v 为终结点且具有不同始结点的数
图10-52
v 1
2
v 3
目为3，其
第(2，3)元素为0，表明那些边既以2v 为终结点又以3v 为终结点，并且具有相同始结点的数目为0。AA T 中的第(2，2)元素为2，表明那些边以2v 为始结点且具有不同终结点的数目为2，其第(2，3)元素为1，表明那些边既以2v 为始结点又以3v 为始结点，并且具有相同终结点的数目为1。
(4)因为=+++=4324A A A A B ???????
?
?001010101100
1010
+
???????
??1100
1110
1020
1110
+
???????
??1020
2120
2210
2120
+
=???
?
??
?
??221
0323
0314
0323
0??
?
?
?
?
?
?
?4340747074701470
，所以
求可达矩阵为???
?
???
??=111011101110
1110
P 。
(5)因为=∧T P P ???????
?
?111011101110
1110
∧??????? ??1111
11111111
0000
＝??
?
?
?
?
?
??1110
11101110
0000
，所以{1v }，{2v ，3v ，4v }构成G 的强分图。
31.画一个无向欧拉图，使它具有： (1)偶数个顶点，偶数条边。 (2)奇数个顶点，奇数条边。 (3)偶数个顶点，奇数条边。 (4)奇数个顶点，偶数条边。
解 (1)n （n 为偶数，且n ≥2）阶圈都是偶数个顶点，偶数条边的无向欧拉图。 (2)n （n 为奇数，且n ≥1）阶圈都是奇数个顶点，奇数条边的无向欧拉图。
(3)在(1)中的圈上任选一个顶点，在此顶点处加一个环，所得图为偶数个顶点，奇数条边无向欧拉图。 (4)在(3)中的圈上任选一个顶点，在此顶点处加一个环，所得图为奇数个顶点，偶数条边无向欧拉图。 32.画一个无向图，使它是： (1)既是欧拉图，又是哈密尔顿图。 (2)是欧拉图，但不是哈密尔顿图。 (3)是哈密尔顿图，但不是欧拉图。 (4)既不是欧拉图，也不是哈密尔顿图。
解 (1)n （n ≥3）阶圈，它们都是欧拉图，又是哈密尔顿图。
(2)给定k （k ≥2）个长度大于等于3的初级回路，即圈1C ，2C …，k C 。将1C 中某个顶点和2C 中的某个顶点重合，但边不重合，
2C 中某个顶点和3C 中的某个顶点重合，但边不重合，续行此法，直到将1 k C 中某个顶点和k C 中的某个顶点重合，但边不重合，设最后得到的连通图为G ，则G 是欧拉图，但不是哈密尔顿图。
(3)在n （n ≥4）阶圈中，找两个不相邻的顶点，在它们之间加一条边，所得图是哈密尔顿图，但不是欧拉图。
(4)在(2)中的图中，设存在长度大于等于4的圈，比如1C ，在1C 中找，两个不相邻的顶点，在它们之间加一条边，然后按照（2）的方法构造图G ，则G 既不是欧拉图，也不是哈密尔顿图。
33.(1)n 为何值时，无向完全图K n 是欧拉图？n 为何值时，K n 仅存在欧拉路而不存在欧拉回路？ (2)什么样的完全二部图是欧拉图？ (3)n 为何值时，轮图W n 为欧拉图？
解 (1)一般情况下，我们不考虑1K 。n （n ≥2）为奇数时，无向完全图K n 是欧拉图。K n 各结点的度均为n －1，若使K n 为偶拉图，n －1必为偶数，因而必n 为奇数。K 2仅存在欧拉路而不存在欧拉回路。
(2)设s r K ,为完全二部图，当r 、s 均为偶数时，s r K ,为欧拉图。
(3)设W n （n ≥4）为轮图，在W n 中，有n －1个结点的度数为3，因而对于任何取值的n （n ≥4），轮图W n 都不是欧拉图。
34.证明：完全图K 9中至少存在彼此无公共边的两条哈密尔顿回路和一条哈密尔顿通路。
证明 设1C 为K 9中一条哈密尔顿回路。令1G 为K 9删除1C 中全部边之后的图，则1G 中每个结点的度均为6。由定理10.26可知1G 仍是哈密尔顿图，因而存在1G 中的哈密尔顿回路2C （显然2C 也是K 9中的哈密尔顿回路，并且1C 与2C 无公共边）。再L 设2G 为1G 中删除2C 中的全部边后所得图，2G 为4正则图。由定理10.26可知2G 具有哈密尔顿通路。设L 为2G 中的一条存在哈密尔顿通路，显然1C 、2C 、L 无公共边。
事实上，可以证明在K 9中存在4条边不重的哈密尔顿回路。
可以证明：在K 3中存在一条边不重合的哈密尔顿回路，K 5中存在两条边不重合的哈密尔顿回路，K 7
中存在3条边不重合的哈密尔顿回路，一般情况下，K 2k+1(k ≥1)中最多可存在条边不重合的哈密尔顿回路。
35.已知a 、b 、c 、d 、e 、f 、g 7个人中，a 会讲英语；b 会讲英语和汉语；c 会讲英语、意大利语和俄语；d 会讲汉语和日语；e 会讲意大利语和德语；f 会讲俄语、日语和法语；g 会讲德语和法语。能否将他们的座位安排在圆桌旁，使得每个人都能与他身边的人交谈？
解 用a 、b 、c 、d 、e 、f 、g 7个结点代表7个人，若两人能交谈（会讲同一种语言），就在代表它们的结点之间连无向边，所得无向
图如下
图（1），此图中存在哈密尔顿回路：，如图（2）粗边所示，于是按图（3）所示的顺序安排座位即可。
36.证明：对于每个竞赛图D，至多改变一条边的方向后就可以变成哈密尔顿图。
证明由定理10.26可知D中存在哈密尔顿通路，设D为n（n≥3）阶竞赛图，
1
v2v…n v为中的一条
哈密尔顿通路，若边<
n
v，1v>在D中，则1v2v…n v1v为D中一条哈密尔顿回路，故D为哈密尔顿图。否
则边<
1
v，n v>在D中，将改变方向得到边
37.给定简单无向图G＝
1-
m
C＋2，则G是哈密尔顿图。
证明若n≥2
1-
m
C＋2，则2n≥m2－3m＋6 （1）。
若存在两个不相邻结点u、v使得d(u)＋d(v)＜m，则有2n＝∑
∈V
w
w
d)
(＜m＋(m－2)(m－3)＋m＝m2－
3m＋6，与（1）矛盾。所以，对于G中任意两个不相邻结点u、v都有d(u)＋d(v)≥m。由定理10.26可知，G是哈密尔顿图。
38.设G是无向连通图，证明：若G中有割点或割边，则G不是哈密尔顿图。
证明若G中有割点v，则G－{v}中至少有两个连通分支，从而(G－{v})＞|{v}|，由定理10.25可知，G不是哈密尔顿图。
若G中有割边e，当G只有两个结点时，显然G不是哈密尔顿图。当G的结点数多余2时，从G中删除割边e之后至少有两个连通分支，其中一个连通分支含有割边e的一个端点v且其结点个数大于1，于是(G－{v})＞|{v}|，由定理10.25可知，G不是哈密尔顿图。
39.某次会议有20人参加，其中每个人都至少有10个朋友，这20人围一圆桌入席，要想使与每个人相邻的两位都是朋友是否可能？根据什么？
解可能。依题意，若用结点代表人，两人是朋友时相应结点之间连一条边，则得到一个无向图G＝
由于对任意u、v∈V，有d(u)＋d(v)≥10＋10＝20，根据定理10.26，G为哈密尔顿图，G中存在哈密尔顿回路，按此回路各点位置入席即为所求。
40.设G是具有k(k＞0)个奇数度结点的无向连通图，证明G中边不重合的简单通路的最小数目是
2
k，它们包含G的全部边。
证明由握手定理的推论可知，k是偶数。对k做归纳法。
(1)当k＝2时，由定理10.22可知，G中存在偶拉路，结论得证。
(2)设k≤2r（r≥2）时结论成立，要证k为2r＋2时结论成立。
设
1
v，2v为G中任意二奇度结点，由G的连通性可知，从1v到2v存在路径0P，删除0P上的全部边，