第10章 图
于是G中共含1＋r1＋r2＋?＋rs＝1＋r＝
k条边不重合的简单通路，它们含G中的全部边。 241.甲、乙、丙、丁四位教师，分配他们教数学、物理，电工和计算机原理四门课。甲能教物理和电工，乙能教数学和计算机原理，丙能教数学、物理和电工，丁只能教电工，对他们的工作怎样分配？
解 设.甲、乙、丙、丁四位教师分别用v1、v2、v3、v4表示，V1＝{v1，v2，v3，v4}，数学、物理，电工和计算机原理四门课分别用u1、u2、u3、u4表示，V2＝{u1，u2，u3，u4}。若vi能教uj，令
v1v2v3v4u1u2u3u442.某杂志发表了7个征求答案的题目，当从读者寄来的解答中挑选每题的两个解答时，编者发现所有14个选出来的解答恰好是7个读者提出来的，而且每个人正好提出了两个答案。试证明：编辑可以这样发表每道题的一个解答，使得在发表的解答中，这7个读者每个人都恰有一个解答。
解 7个位读者分别用v1、v2、?、v7表示，V1＝{v1，v2，?，v7}，7个题目分别用u1、u2、?、
u7表示V2＝{u1，u2，?，u7}。若vi为uj做解答，令
二部图。由已知条件可知V1中每个结点关联两条边，中每个结点也关联两条边，即G满足t＝2的“t条件”，所以存在V1到V2的完备匹配，又因为|V1|＝|V2|，因而对于任意的V1到V2的完备匹配M，不存在M-非饱和点，故M也是完全匹配。即使得7个题目的7个解答分别由7个读者给出是办得到的。
43.给定二部图G＝
2证明 设|V1|＝m1，则|V2|＝m－m1，于是n≤m1(m－m1)＝m1m－m1。因为(?m1)2?0，即
2
m2m222，所以n≤m/4。 ?mm1?m1444.设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）
23 13
第10章 图
将（2）其代入（1）得2＜m－m＋12，m＜30。 （3） 若所有的面均至少由5条边围成，则
5r≤2m，r≤m， （4） 将（2）、（4）代入（1）得
2≤m－m＋m，m≥30。 （5） （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，?，k23252325。
若存在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。
下面用反证法证明结论。若不然，G中所有结点的度数均大于等于5，由握手定理可知2m＝
2525?d(v)kk?1n≥5n，所以n≤m，将其代入m≤3n－6得m≤3×m－6，于是m≥30，与m＜30矛盾，所以一定存在结点v使得d(v)≤4。
14
第10章 图
48.设G为有k(k≥2)个连通分支的平面图，G的平面图的每个面至少由f(f≥3)条边围成，则m≤
f(n－k－1)。 f?2解 设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≤
f(n－k－1)。 f?2*
49.证明：平面图G的对偶图G是欧拉图?G中每个面的次数均为偶数。
证明 显然G是连通图，设v*为G*的任一结点，v*位于G的面R中，由于R由偶数边围成，所以d(v*)为偶数，由v*的任意性可知，G是欧拉图。
50.在由6个结点，12条边构成的连通平面图G中，每个面由几条边围成？为什么？
解 每个面由3条边围成。因图中结点数和边数分别为n＝6，m＝12。根据欧拉公式n－m＋r＝2得r＝8。
又因为围成。
51.给定连通简单平面图G＝
f?F*
*
?d(v)＝2m＝24，而简单连通平面图的每个面至少由3条边围成，所以G中每个面由3条边
i2|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(v)＝3×3＋2×1＋1×x＝11＋x。由握手定理得11＋x＝2m＝6＋2x，于是x＝5。所
ii?1n以T中有5个1度结点。
(2)下图中所示的两棵树均满足要求，但它们是不同构的。
15
第10章 图
54.一棵无向树T有ni个度数为i的结点，i＝2，3，?，k，问有多少个1度结点？ 解 设T中有x个1度结点，则T中结点数n＝
nkk
?n＋x，T中边数m＝?n＋x－1。T中各结点度
iii?2i?2kk数之和
k
?d(v)＝?i*n＋1×x＝?i*n＋x。由握手定理得
iii
i?1i?2i?2
kkiii?2i?32(
?ni?2ki＋x－1)＝
?i*n＋x，于是
i
i?2
k
x＝
?i*n－2?n＋2＝?(i?2)*n＋2。
i
i?2
所以T中有
?(i?2)*n＋2个1度结点。
ii?3k55.证明恰有两个结点的度数为1的树必为一条通路。
证明 设T为一棵具有两个1度结点的树（n，m），则m＝n－1且有
n?d(v)＝2m＝2(n－1)。又T
ii?1n?2i?1in连通且除两个1度结点外，其他结点度数均大于等于2，而
n?2i?1n?2i?1?d(v)＝2＋?d(v)，有
ii?12(n－1)＝2＋
?d(v)，故?d(v)＝2(n－1)。因此n－2个分支结点的度数都恰为2，即T为一条通路。
ii56.设无向图G是由k(k≥2)棵树构成的森林，至少在G中添加多少条边才能使G成为一棵树？ 解 设G的k个连通分支为T1、T2、?、Tk，设结点vi∈Ti，i＝1，2，?，k。在G中添加边(vi，vi?1)，i＝1，2，?，k，设所得图为T，则T连通且无回路，因而T是树。所以边的添加数k－1是使得G为树的最小数目。
57.试画出4个结点和5个结点的所有非同构的无向树。
解 4个结点的所有非同构的无向树有2棵，如图（1）和（2）所示。5个结点的所有非同构的无向树有3棵，如图（3）、（4）和（5）所示。
（1）
（2）（3）16
（4）（5）