第10章 图
(4)在(2)中的图中，设存在长度大于等于4的圈，比如C1，在C1中找，两个不相邻的顶点，在它们之间加一条边，然后按照（2）的方法构造图G，则G既不是欧拉图，也不是哈密尔顿图。
33.(1)n为何值时，无向完全图Kn是欧拉图？n为何值时，Kn仅存在欧拉路而不存在欧拉回路？ (2)什么样的完全二部图是欧拉图？ (3)n为何值时，轮图Wn为欧拉图？
解 (1)一般情况下，我们不考虑K1。n（n≥2）为奇数时，无向完全图Kn是欧拉图。Kn各结点的度均为n－1，若使Kn为偶拉图，n－1必为偶数，因而必n为奇数。K2仅存在欧拉路而不存在欧拉回路。
(2)设Kr,s为完全二部图，当r、s均为偶数时，Kr,s为欧拉图。
(3)设Wn（n≥4）为轮图，在Wn中，有n－1个结点的度数为3，因而对于任何取值的n（n≥4），轮图Wn都不是欧拉图。
34.证明：完全图K9中至少存在彼此无公共边的两条哈密尔顿回路和一条哈密尔顿通路。
证明 设C1为K9中一条哈密尔顿回路。令G1为K9删除C1中全部边之后的图，则G1中每个结点的度均为6。由定理10.26可知G1仍是哈密尔顿图，因而存在G1中的哈密尔顿回路C2（显然C2也是K9中的哈密尔顿回路，并且C1与C2无公共边）。再L设G2为G1中删除C2中的全部边后所得图，G2为4正则图。由定理10.26可知G2具有哈密尔顿通路。设L为G2中的一条存在哈密尔顿通路，显然C1、C2、L无公共边。
事实上，可以证明在K9中存在4条边不重的哈密尔顿回路。
可以证明：在K3中存在一条边不重合的哈密尔顿回路，K5中存在两条边不重合的哈密尔顿回路，K7
中存在3条边不重合的哈密尔顿回路，一般情况下，K2k+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）阶竞赛图，v1哈密尔顿通路，若边
?vnv1为D中一条哈密尔顿回路，故D为哈密尔顿图。否则
边
11
第10章 图
237.给定简单无向图G＝
22证明 若n≥Cm?1＋2，则2n≥m－3m＋6 （1）。
若存在两个不相邻结点u、v使得d(u)＋d(v)＜m，则有2n＝?d(w)＜m＋(m－2)(m－3)＋m＝m2
w?V－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中边不重合的简单通路的最小数目是它们包含G的全部边。
证明 由握手定理的推论可知，k是偶数。对k做归纳法。 (1)当k＝2时，由定理10.22可知，G中存在偶拉路，结论得证。 (2)设k≤2r（r≥2）时结论成立，要证k为2r＋2时结论成立。
设v1，v2为G中任意二奇度结点，由G的连通性可知，从v1到v2存在路径P0，删除P0上的全部边，得连通分支G1，G2，?，Gs。这些连通分支共含2r个奇度结点，设Gi中含ri个奇度结点，则2ri≤2r（1
sk2，
≤r≤s），且?2ri＝2r。由归纳假设可知，Gi中存在ri条边不重合的简单通路，它们含Gi中的所有边。于
i?1是G中共含1＋r1＋r2＋?＋rs＝1＋r＝
k2条边不重合的简单通路，它们含G中的全部边。
41.甲、乙、丙、丁四位教师，分配他们教数学、物理，电工和计算机原理四门课。甲能教物理和电工，乙能教数学和计算机原理，丙能教数学、物理和电工，丁只能教电工，对他们的工作怎样分配？
解 设.甲、乙、丙、丁四位教师分别用v1、v2、v3、v4表示，V1＝{v1，v2，v3，v4}，数学、物理，电工和计算机原理四门课分别用u1、
u1u2u3u4u2、u3、u4表示，V2＝{u1，u2，u3，
12 v1v2v3v4第10章 图
u4}。若vi能教uj，令
异性条件”，且|V1|＝|V2|，所以，存在V1到V2的完全匹配。图中粗线所示就是其一种分配方案。
42.某杂志发表了7个征求答案的题目，当从读者寄来的解答中挑选每题的两个解答时，编者发现所有14个选出来的解答恰好是7个读者提出来的，而且每个人正好提出了两个答案。试证明：编辑可以这样发表每道题的一个解答，使得在发表的解答中，这7个读者每个人都恰有一个解答。
解 7个位读者分别用v1、v2、?、v7表示，V1＝{v1，v2，?，v7}，7个题目分别用u1、u2、?、u7表示V2＝{u1，u2，?，u7}。若vi为uj做解答，令
43.给定二部图G＝
m2?m1)2?0，即
4?mm1?m12，所以n≤m/4。
2
44.设G是面数r小于12的简单平面图，G中每个结点的度数至少为3。 (1)证明G中存在至多由4条边围成的面。
(2)给出一个例子说明，若G中的面数为12，且每个结点的度至少为3，则(1)的结论不成立。 证明 1)不妨设G是连通的，否则可以对它的每个连通分支进行讨论（因为每个连通分支均满足条件）。因而由偶拉公式有
n－m＋r＝2， （1）
又由已知条件得r＜12且n≤m， （2）
32将（2）其代入（1）得2＜m－m＋12，m＜30。 （3）
32若所有的面均至少由5条边围成，则
5r≤2m，r≤m， （4）
52将（2）、（4）代入（1）得
2≤m－m＋m，m≥30。 （5）
3522 13
第10章 图
（3）与（5）是矛盾的，因而必存在至多由4条边围成的面。
2)十二面体图有12个面，每个结点均为3度，每个面由5条边围成，并没有4条边围成的面。 45.把平面分成?个区域，每两个区域都相邻，问?最大为几？
解 在每个区域放一个结点，当两区域相邻时就在相应的两个结点之间连一条线，如此构造了一个平面图且是完全图K?，而最大的平面完全图为K4，所以?最大为4。
46.设简单平面图G中结点数n＝7,边数m＝15，证明G是连通的。
证明 反证法。设G为非连通的，具有k≥2个连通分支G1,G2,?,Gk。设Gi的结点数为ni，边数为
mi，i＝1，2，?，k。
若存在nj＝1，则k必为2，因为只有此时G为一个平凡图并上一个K6才能使其边数为15，可是K6不是平凡图，这矛盾于G为平面图这个事实，所以不存在nj＝1。
若存在nj＝2，Gj中至少有一条边（因为G为简单图），另外5个结点构成K5时边数最多，但充其量为10条边，这与G有15条边矛盾。
综上所述，ni必大于等于3，i＝1，2，?，k。由定理10.37可知，mi≤3（ni－2）＝3ni－6，i＝1，2，?，k。求和得
m≤3n－6k （1）
将n＝7,m＝15代入（1）得15≤21－6k，于是k≤1，这与k≥2矛盾。 至此证明了G必为连通图。
47.设G是边数m小于30的简单平面图，试证明G中存在结点v使得d(v)≤4。
解 不妨设G是连通的，否则因为它的每个连通分支的边数都应小于30，因此可对它的每个连通分支进行讨论，所以可设G是连通的。
若G中无回路，则G必为树，结论显然成立。若G中有回路，由于G为简单图，因而G中每个面至少由3个边围成，由定理10.37有m≤3n－6。
n下面用反证法证明结论。若不然，G中所有结点的度数均大于等于5，由握手定理可知2m＝?k?1d(vk)≥
5n，所以n≤m，将其代入m≤3n－6得m≤3×m－6，于是m≥30，与m＜30矛盾，所以一定存在结
5522点v使得d(v)≤4。
48.设G为有k(k≥2)个连通分支的平面图，G的平面图的每个面至少由f(f≥3)条边围成，则m≤
ff?2(n－k－1)。
解 设G的各面的边界长度之和为T。G的每条边在计算T时，均提供2，又因为G的平面图G? 的每个面至少由f条边围成，所以fr≤T＝2m。又因为r＝k＋1＋m－n，将其代入fr≤2m得f(k＋1＋m－n)≤2m，整理得m≤
ff?2(n－k－1)。
14
第10章 图
49.证明：平面图G的对偶图G*是欧拉图?G中每个面的次数均为偶数。
*证明 显然G*是连通图，设v*为G*的任一结点，由于R由偶数边围成，所以d(v*)v位于G的面R中，
为偶数，由v*的任意性可知，G*是欧拉图。
50.在由6个结点，12条边构成的连通平面图G中，每个面由几条边围成？为什么？
解 每个面由3条边围成。因图中结点数和边数分别为n＝6，m＝12。根据欧拉公式n－m＋r＝2得r＝8。
又因为?d(vi)＝2m＝24，而简单连通平面图的每个面至少由3条边围成，所以G中每个面由3条边围成。
51.给定连通简单平面图G＝
f?F2|E|＝24。若存在f∈F，使得d(f)＞3，则3|F|＜2|E|＝24，于是|F|＜8，与|F|＝8矛盾。故对任意f∈F，d(f)＝3。
52.证明：不存在具有5个面，每两个面都共享一条公共边的平面图G。
证明 若存在这样的平面图G，设G的对偶图为G*，则G*也是平面图。由于G有5个面，所以G*具有5个结点。设v*为G*的任一结点，设它位于G的面R中。由于R与其余4个面均有公共边，所以v*与其余面中的结点均相邻，于是d(v*)＝4，而且G*为简单图，所以G*必为K5，可是K5为非平面图，这与G*为平面图矛盾。
53.已知一棵无向树T有三个3度结点，一个2度结点，其余的都是1度结点。 (1)T中有几个1度结点？
(2)试画出两棵满足上述度数要求的非同构的无向树。
解 (1)设T中有x个1度结点，则T中结点数n＝3＋1＋x，T中边数m＝3＋1＋x－1＝3＋x。T中各结点度数之和?d(vi)＝3×3＋2×1＋1×x＝11＋x。由握手定理得11＋x＝2m＝6＋2x，于是x＝5。所以T
i?1n中有5个1度结点。
(2)下图中所示的两棵树均满足要求，但它们是不同构的。
54.一棵无向树T有ni个度数为i的结点，i＝2，3，?，k，问有多少个1度结点？
15