第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