习题十
1. 设G 是一个(n ，m)简单图。证明：，等号成立当且仅当G 是完全图。
证明：（1）先证结论：
因为G 是简单图，所以G 的结点度上限 max(d(v)) ≤ n-1, G 图的总点度上限为 max(Σ(d(v)) ≤ n ﹒max(d(v)) ≤ n(n-1) 。根据握手定理，G 图边的上限为 max(m) ≤ n(n-1)/2,所以。
（2） =〉G 是完全图
因为G 具有上限边数，假设有结点的点度小于n-1,那么G 的总度数就小于上限值，边数就小于上限值，与条件矛盾。所以，G 的每个结点的点度都为n-1，G 为完全图。 G 是完全图 =〉
因为G 是完全图，所以每个结点的点度为n-1, 总度数为n(n-1)，根据握手定理，图G 的边数 。■
2. 设G 是一个（n ，n +1）的无向图，证明G 中存在顶点u ，d （u ）≥3。
证明：反证法，假设,则G 的总点度上限为max(Σ(d(u)) ≤2 n ，根据握手定理，图边的上限为max(m) ≤ 2n/2=n 。与题设m = n+1，矛盾。因此，G 中存在顶点u ，d （u ）≥3。■
3．确定下面的序列中哪些是图的序列，若是图的序列，画出一个对应的图来: （1）（3，2，0，1，5）； （2）（6，3，3，2，2） （3）（4，4，2，2，4）； （4）（7，6，8，3，9，5）
解：除序列（1）不是图序列外，其余的都是图序列。因为在（1）中，总和为奇数，不满足图总度数为偶数的握手定理。
可以按如下方法构造满足要求的图：序列中每个数字ai 对应一个点，如果序列数字是偶数，那么就在对应的点上画ai/2个环，如果序列是奇数，那么在对应的点上画(ai-1)/2个环。最后，将奇数序列对应的点两两一组，添加连线即可。下面以（2）为例说明：
(6 , 3, 3, 2, 2 ) 对应图G 的点集合V= { v 1,v 2,v 3,v 4,v 5}
每个结点对应的环数(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1)
将奇数3，3 对应的结点v 2,v 3一组，画一条连线
其他序列可以类式作图，当然大家也可以画图其它不同的图形。■
4．证明：在（n ，m ）图中。
证明：图的点度数是一组非负整数{d(v 1),d(v 2)…d(v n )}，那么这组数的算术平均值一定大于等于其中的最小值，同时小于等于其中的最大值。对应到图的术语及为：最大值为，最小值为δ，平均值 = (d(v 1)+d(v 2)…+d(v n ))/n = 2m/n,所以。■
5．证明定理10.2。
【定理10.2】 对于任何（n ,m ）有向图G =（V ，E ），
证明：有向图中,每条有向边为图贡献一度出度，同时贡献一度出度，所以总出度和总入度相等，并和边数相等。因此，上述关系等式成立。■
6．设G 是（n ，m ）简单二部图，证明：。
证明：本题目，我们是需要说明n 阶的简单二部图的边数的最大值 = 即可。
设n 阶的简单二部图，其两部分结点集合分别为V1，V2,那么|V1| + |V2| = n 。此种情况下，当G 为完全二部图时，有最多的边数，即max(m) = |V1||V2|,变形为，max(m) =( n-|V2|)|V2|.此函数的最大值及为n 阶二部图的边的上限值，其上限值为当|V2|=n/2 时取得。及max(max(m)) = ,所以n 阶二部图(n,m), ■
7. 无向图G有21条边，12个3度数结点，其余结点的度数均为2，求G的阶数n。
解：根据握手定理有： 21 =( 3Χ12 + 2(n-12))/2, 解此方程得n = 15■
8．证明：完全图的点诱导子图也是完全图。
证明：方法1
为证明此结论，我们先证两个引论：
引论1：设G(V,E)为母图，,则G的任意子图G'(V’,E’)是G关于V’的点诱导子图G''(V’,E’’)的子图。
引论2：引论1中G’’(V’,E’’)的任意点诱导子图，也是G图的点诱导子图。
证明：略，请读者证明。
设有完全图Kn( n≥1),现根据其p阶点诱导子图作归纳证明。
Kn的1阶点诱导子图，显然是完全图，且都是K1图。当n≥2，Kn的2阶点诱导子图，显然是完全图，且都是K2图
假设Kn的p(n>p>2)阶点诱导子图，为Kp图，那么对任意的p+1阶点诱导子图G，根据引理2结论，G的任意p阶点诱导子图G’为Kn的p阶点诱导子图，且为Kp图。因此，G 必为Kp+1图。
根据以上论证可得原命题成立■
方法2
因为完全图的任意两个顶点均邻接，所以点导出子图任意两个顶点也邻接，为完全图。■9．若，称G是自补图。确定一个图为自补图的最低条件；画出一个自补图来。
解：设G为(n,m)图，为(n,m`)图，根据补图的定义有，至少应该满足
m+m`=n(n-1)/2 (1) 根据同构的定义有，至少应该满足
m=m` (2)
(1),(2)联立求解得：m=n(n-1)/4, 及一个图为自补图，最低条件为结点数为4的倍数或为4的倍数加1。
图示略■
10．判断图10.29中的两个图是否同构，并说明理由。
图9-1.15
图10.29
解：题中两个图不同构，因为左边图的唯一3度点有2个1度点为其邻接点，而右图唯一的3度点只有1个1度点为其邻接点。因此这两个图不可能同构■
11．证明：图10.30中的两个图是同构的。
解：略■
12. 求具有4个结点完全图K 4的所有非同构的生成子图。
解：我们可以把生成子图按总度数不同进行分类，不同总度数的子图类决不同构。总度数相同的子图类中，再去找出不同购的子图。因此求解如下： Σd(v) = 0: (0,0,0,0) =2: (1,1,0,0)
=4: (2,1,1,0) (1,1,1,1)
=6: (3,1,1,1) (2,2,1,1)(2,2,2,0) =8: (2,2,2,2) (3,2,2,1) =10: (3,3,2,2) =12: (3,3,3,3) 总共10个不同构生成子图■
13. 设有向图D=
(1) 在图中找出所有长度分别为1，2，3，4的圈 (至少用一种表示法写出它们，并以子图形式画出它们)。
(2) 在图中找出所有长度分别为3，4，5，6的回路，并以子图形式画出它们。 解：
(1)
图10.30
(2)子图略
长度为三的回路：Ae 1Ae 1Ae 1A,Ae 1Ae 3De 2A,Ae 4Be 7Ce 5A,Ae 4Be 8Ce 5A
长度为四的回路：AAAAA ，AAADA ，AABe 7CA,AABe 8CA,ABe 7CDA,ABe 8CDA
长度为五的回路：AAAAAA,AAAADA,AAABe 7CA,AAABe 8CA,AABe 7CDA,AABe 8CDA, AADADA,AAAe 4Be 7Ce 5A,AAAe 4Be 8Ce 5A, ADAe 4Be 7Ce 5A,ADAe 4Be 8Ce 5A ■
14. 试证明在任意6个人的组里，存在3个人相互认识，或者存在3个人相互不认识。
证明：设A 为6人中的任一人，那么A 要么至少与3人认识，要么至少与3人不认识，二者必居其一。
假设A 与B ，C ，D 三人认识，如果B ，C ，D 三人互不认识，结论成立
如果B ，C ，D 三人中，至少有两人相互认识，则它们和A 一起，构成相互认识的3人，结论成立。
同理，A 至少与3人不认识，结论也成立。因此，题设结论成立■
15. 若u 和v 是图G 中仅有的两个奇数度结点,证明u 和v 必是连通的。
证明：反证法，假设u 和v 不连通，那么他们必然分布于此图的两个连通分支中。那么它们将分别是各连通分支中唯一的奇数度结点。根据握手定理，一个图中奇度点的个数为偶数。而两个连通分支中，奇度点的个数为奇数。矛盾。矛盾的产生，是由于假设不连通导致的，因此，题设结论成立■
16. 证明:G 是二部图当且仅当G 的回路都是偶长回路。
证明：设二部图G ，顶点分为两个集合V1 ，V2 充分性：
先证明在二部图中，奇长路的道路的两个端节点一定分别在两个顶点集合中，对道路长度使用归纳法，
（1） 当道路长度为1是，根据二部图的定义，每条边的两个顶点分别在两个点集合中，
结论成立
（2） 假设道路长度为2n-1 ( n ≥2)时结论成立
（3） 当道路长度为2n+1时，设P=v 1v 2…v 2n-1v 2n v 2n+1,在此路径上删除最后两个结点，
那么
道路P将变为长度为2n-1的奇长道路，根据假设，v
1,v2n-1分别在两个顶点集合中，那么v2n和v1在同一顶点集合中，而v2n+1和v1在不同顶点集合，结论成立
因为G中的任何回路，写成道路的形式，起点和终点时一个结点，当然在同一个顶点集合中，因此长度必为偶数；
必要性：（仅对连通分支证明）
在图中任意取一点着色为白色，将和此点最短距离为奇数的点着色为黑点，为偶数的着色为白点，那么将结点分为白色和黑色连个点集，任何同色点之间没有边相连。否则将形成奇数长度的回路，例如同色结点v1，v2 相邻，那么从初始着色点v开始通过最短路径可以形成如下回路v…v1v2…v,因为v…v1,v2…v长度和为偶数，那么回路v…v1v2…v长度为奇数，与题设矛盾。所以是二部图
17.设(n, m)简单图G满足,证明G必是连通图。构造一个的非连通简单图。
证明：假设G不连通，分支G1，G2．．Ｇｋ，那么他们的边数的最大值ｍａｘ（ｍ）＝Σ（ｎｉ－１）ｎｉ／２≤Σ（ｎｉ－１）（ｎ－１）／２＝（ｎ－１）／２Σ（ｎｉ－１）＝（ｎ－１）（ｎ－ｋ）／２，所以，只有当k=1时，才能满足题设要求，G是连通图。如果将顶点集合分成两个点集，|V1|=1，|V2|=n-1,构成如下的有两个分支的非连通简单图，G1=（1，0），G2=Kn-1,满足题设条件■
18. 设G是阶数不小于3的连通图。证明下面四条命题相互等价:
(1）G无割边；
(2) G中任何两个结点位于同一回路中；
(3) G中任何一结点和任何一边都位于同一回路中；
(4) G中任何两边都在同一回路中。
证明：（1）=〉（2）
因为G连通，且G无割边，所以任意两个结点u,v，都存在简单道路p=u…wv.又因为G无割边，所以，删除边wv后，子图依然连通，即w,v存在简单道路p’,以此类推，可以找到一条核p每条边都不相同的p’’=v…u,这样p和p’’就构成了一条回路。
（2）=〉（3）
因为G中任意两个结点都位于同一回路中，所以任意结点u,和任意边e的两个端点v1,v2都分别在两个回路C1，C2中，如果C1=C2=u…v1…v2…u,那么将回路中v1…v2,用v1v2=e 替换，就得到新的新的回路，并满足要求。如果C1≠C2，C1=u…v1…u,C2=u…v2…u,那么构成新的道路P=u…v1…u…v2…u,在其中将重复边剔出掉，得到新的回路C3，其中包含v1,v2结点，可以将回路中v1…v2用v1v2=e替换，就得到新的新的回路，并满足要求.
（3）=〉（4）
对任意两条边e1,e2其端点分别为u1,u2,v1,v2。根据（3）存在回路C1 = u1…v1v2…u1,C2=u2…v1v2…u2。那么可以形成新的闭道路P=u1…v1v2…u2…v1v2…u1,在其中将重复边剔出到，得到新的回路C3，其中包含e2和u1,u2结点，可以将回路中u1…u2用u1u2=e1替换，就得到新的新的回路，包含e1,e2,满足要求.
(4)=>(1)
因为任意两条边都在同一回路中，所以不存在割边。假设边e是割边，那么删除此边，图不连通，分支中的任何一对不在同一分支中的边，不能构成回路，与条件矛盾。所以，G中无割边■
19. 设G=(V,E)是点度均为偶数的连通图。证明:对任何。
证明：G-v最多产生d(v)个奇数度点，又因为每个连通分支中奇数度点的个数是偶数，即G-v的连通分支最少有两条边和v相连，所以总连通分支数小于等于d(v)/2■
20. 证明:图中距离满足欧几里德距离的三条公理。
证明：（1）d(u,v)≥0,即任何两个结点之间的最短路长度大于等于0
显然，结点ｕ与自己之间的距离为０，而和其他结点之间的最短距离不为０。
（２）ｄ（ｕ，ｖ）＝ｄ（ｖ，ｕ），两个结点之间的最短距离相等
显然，如果长度为ｋ的最短道路p=u…v ，即使u到v的最短道路，也是v到u的最短道路。（3）d(u,v)+d(v,w)≥d(u,w)
假设d(u,v)+d(v,w)≤d(u,w)，那么最短道路P=u…w ,就不是最短道路，因为另一条道路p’=u…v…w其长度小于Ｐ，与最短道路相矛盾，因此原结论存立■
21. 证明:在非平凡连通图G中,e为割边的充要条件是它不包含于G的任何圈中。
证明：1）e为割边 =〉e不包含于G的任何圈中
假设e包含在某一圈Ci中，那么删除此边，但边关联的两个邻接点依然连通，所以没有破坏原图的连通性。因此不是割边，矛盾。所以假设不成立，既e不包含于G的任何圈中；
2）e不包含于G的任何圈中 =〉e为割边
假设e为割边，那么删除此边，生成子图依然连通。e关联的两个邻接点有基本道路存在，此基本道路连同e构成一个圈。与题设矛盾。所以假设不成立，既e为割边。
根据1），2)可知，题设结论成立■
22. 证明:若G是3度正则的简单图,则。（请冯老师帮助解答下）
证明：
23. 证明:在具有n（n≥2）个结点的简单无向图G中，至少有两个结点的度数相同。
证明：此题可用鸽笼原理，因为n个结点的简单无向图G中，结点的度数只可能是0，1，2…n-1这n个数，又因为如果有结点的度数为0，那么就不可能有结点的度为n-1，反之也然。所以n 个结点，最多有n-1种度数，其中必有至少两个结点的度数相同■
24. 设G是的简单图。证明:G中必有长度至少为的圈。
证明：设ｐ＝ｕ．．．ｖ是满足题设要求图Ｇ中的最长基本道路，那么ｄ（ｕ），ｄ（ｖ）都应该大于等于δ。那么，u,v的邻接点都应该在道路p 上，否则此道路可以延长，与其是最长路假设矛盾。如果u，v是邻结点，那么可以构成一个圈c= u…vu，其长度≥δ＋１。如果ｕ，ｖ不是邻结点，那么从ｐ的终点开始删除点，直到其为ｕ的邻结点为止，得到道路ｐ＇,可知道路p’，依然保持ｕ的所有邻结点都在ｐ＇上的性质，所以可构成一个圈ｃ＇＝ｕ．．．ｕ＇ｕ，其长度
≥δ＋１，证毕■
25. 证明:G 是单向连通图当且仅当存在一条包含G 中全部结点的有向道路。
证明：假设不存在包含全部结点的有向道路，那么设ｐ＝ｖ１ｖ２．．．ｖｋ是Ｇ中最长的有向道路，且ｕ结点不包含在此有向道路中。ｕ和此道路中任何中间结点都不可能双向可达，且ｕ不能到达ｖ１，且ｖｋ也不能到达ｕ，否则，此最长路可扩充。那么由于道路上的每个结点和ｕ都单向可达，所以此最长路和ｕ之间的可达关系必然如下图所示：
当ｋ为偶数时，道路可扩充为v 1…v k/2…u …v k/2+1…v k ,而当ｋ为奇数时，不管ｖｋ＋１／２与ｕ之间是如何单向可达的，都可以构造出更长的有向道路，矛盾，所以Ｇ中一定存在包含所有结点的有向道路■
26. 无向图G 如图10.32所示，先将此图顶点和边标出，然后求图中的全部割点和割边。
图10.32 解：
标注如下所示：
根据标记后的图，可求得割点分别为：ｕ４，ｕ７，ｕ８，割边分别为：ｕ４ｕ５，ｕ７ｕ８，ｕ８ｕ９■
27. 求图10.33的全部强分图和单向分图。
图10.33
解：将图重新标记如下：
那么此图的邻接矩阵为，通过计算可求得其强分图矩阵为：
因此，此图有两个强分图，一个包含一个结点Ｖ９ ，一个包含其它的８个节点。由于两个强分图之间存在有向道路，因此全部９个结点，构成了单向分图■
28. 证明：一个连同无向简单图中，任意两条最长路至少有一个公共顶点。