离散数学（图论部分）1-4章习题课
1. 证明：在10个人中，或有3人互相认识，或有4人互不认识。
证：设x为10人中之任意某人，则在余下9人中：(1) x至少认识其中4人，或(2) x至多认识其中3人（即至少不认识其中6人），两者必居其一。 (1) 若此x认识的4人互不相识，命题得证；否则，互相认识的2人加上x构成互相认识的3人，命题得证。
(2) 若此x不认识的6人中有3人互相认识，命题得证；否则，由Ramsey(3,3)=6知，此6人中至少有3人互不认识，此3人加上x为互不认识的4人，命题得证。
2. 设 (a) V={a,b,c,d}，A={,,
(b) V={a,b,c,d,e}，E={(a,b),(a,c),(b,c),(d,e)} 画出上述图的图解。 解：略。
3. 试找出K3的全部子图，并指出哪些是生成子图。
解：K3共有17个子图。其他略。
4. 证明：在至少有2人的团体中，总存在2个人，他们在这个团体中恰有相同数目的朋友。
解：在n个人的团体中，各人可能有的朋友数目为0, 1, 2, 3, …, n?1，共n个数，但其中0和n?1 不能共存，故n个人事实上可能的朋友数目只有n?1个。由鸽巢原理，命题得证。
5. 某次宴会上许多人互相握手。证明：必有偶数个人握了奇数次手。
证：以人为顶点，握手关系为邻接关系构造一个无向图。由图的性质，奇数度的顶点必为偶数个，即握了奇数次手的人数必为偶数。 6. 证明：Ramsey(3,4)=9。（提示：题1的推广）
证：在9个人中，不可能每个人都恰好认识其他的3个人（即图的9个顶点不
可能每个顶点的度都为3，否则违反图的奇数度的顶点必为偶数个的性质）。设x不会恰好认识其他的3个人（即deg(x)?3），则在余下8人中：：(1) x至少认识其中4人，或(2) x至多认识其中2人（即至少不认识其中6人），两者必居其一。由题1的过程，命题得证。
7. 证明：图G=(V, E)，n=|V|，m=|E|。若m?(n?1)(n?2)，则G连通
证：利用反证法。设G可分解为不连通的非空的两部分G1= (V1, E1 )、G2 = (V2,
E2 )，并设 n1=|V1|?0，m1=|E1|， n2=|V2|?0，m2=|E2| 则 n=n1+n2，m=m1+m2
若 G1为完全图，则 m1=n1(n1?1)，故 m1?n1(n1?1) 若 G2为完全图，则 m2=n2(n2?1)，故 m2?n2(n2?1) 故：m= m1+m2
?n1(n1?1)+n2(n2?1)
=(n?1)(n?2)+(n1?1)(n1?n+1) 又：1?n1?n?1 故：(n1?1)(n1?n+1)?0
即：m?(n?1)(n?2) 与条件m?(n?1)(n?2) 矛盾。
8. 证明：图G = ( V, E )，n=|V|，m=|E|。若G连通，则m?(n?1) 证一：对n做归纳。 n=2时，m=1?n?1成立 设 n=k时，命题成立。 当n=K+1时，
由于G连通，任意顶点的度?1；
12121212121212121212(1) 若任意顶点的度?2，则 2m=?deg(vi) ?2n，此时 m?n?n?1，命题成立。
(2) 否则，若有某顶点u的度为1，从图中去掉该顶点以及其关联边，得到的新图
G1 = (V1, E1) 仍然连通，且 n1=|V1|= n?1=K，m1=|E1|= m?1 由归纳假设，对图G1有 m1?(n1?1) 即 m?1?(n?1?1) 或 m?(n?1)
由归纳原理，命题得证。
证二：由于G连通，设T= ( V, E? ) 是G的一棵生成树，则 |E?|=n?1，而 m?|E?|，故。
9. 证明：n个人中，若任何2人合在一起认识其他n?2个人，则他们可以排成一排，使除首尾2人外，其余的人都和相邻的人认识。
证：以人为顶点，认识关系为邻接关系构造一个无向图，问题转化为讨论满足条件的图中Hamilton道路的存在性。
从图中任取2个顶点x和y，记deg(x,y) 为 {x,y} 与其他顶点的邻接边数目。由题意，有 deg(x,y)?n?2，这里的n?2由除了x和y外的n?2顶点中每个顶点贡献一条与x或y邻接的边得到。 (1) 若x与y认识，则
deg(x)+deg(y) = deg(x,y)+2 ? n?2+2 = n ? n?1
(2) 若x与y不认识，设x认识z，z?y，由题意x与z合在一起认识包括y的其他n?2个人，所以只能z也认识y，即在图中，顶点z与x和y同时邻接。由之前deg(x,y) ? n?2的讨论可得：
deg(x,y) ? n?2+1 = n?1， 故 deg(x)+deg(y) = deg(x,y) ? n?1
综上，对任意顶点x和y，有deg(x)+deg(y) ? n?1，由Hamilton道路存
在的充分条件知图中存在一条Hamilton道路，命题得证。 10. 用Warshall算法求下图的道路矩阵： 解：见课件的举例。
11. 若树中恰有2个顶点的度为1，则此树为一条链。 证：设 T= (V, E) 为一棵树，n=|V|，m=|E|，则 m=n?1
故：?deg(vi)?2m?2(n?1) 且 deg (vi) ?0 (i =1..n)
vi?V不妨设 deg (v1)= deg (vn)=1， 则
?deg(v)?2(n?1)?2?2(n?2)且 deg (vi) >1 (i =2..n?1)
ii?2n?1所以只能 deg (vi) =2 (i =2..n?1) 即此树为从v1到vn的一条路。
12. 若树中有一顶点的度为k，则树中至少有 k个度为1的点。 证：设 T= (V, E) 为一棵树，n=|V|，m=|E|，则 m=n?1
故：
?deg(v)?2m?2(n?1) 且 deg (v) ?0 (i =1..n)
ii?1ni
不妨设 deg (vn) =k，则
?deg(v)?2(n?1)?k
ii?1n?1设树中有p个度为1的顶点：deg (vn?1) = deg (vn?2)= deg (vn-p)=1
n?p?1则 或
?deg(v)?p?2(n?1)?k
ii?1n?p?1i?1?deg(v)?2(n?1)?k?p
i对余下的n?p?1个顶点，每个顶点的度至少为2，即
n?p?1
?degv(?)ii?1n2?(p? 1)所以 2(n?1)?k?p ? 2(n?p?1)
解不等式得：p ? k
13. 设连通图G=(V, E)，T=(V, E(T))和T'=(V, E(T'))是G的两棵不同生成树且 e?E(T)?E(T')，则存在一条边 e'?E(T')?E(T)，使得 T?e+e' 和 T'?e'+e 都是G的生成树。
证：从T中去掉边e，则T被分成不连通的两部分，设其顶点集分别为V1和V2。在T'中必存在连接V1和V2的边，记为e'?E(T')。 ∵ e?E(T)?E(T') 即 e?E(T') ∴ e'? e
又：若e'?E(T)，则e不是T中割边，与T是一棵树矛盾。 ∴ e'?E(T) 即 e'?E(T')?E(T)
考察 T+e'，e和e' 在其中唯一的回路上，因此T?e+e' 构成G的一棵生成树。 同理，考察 T'+e，可知 T'?e'+e 也构成G的一棵生成树。
14. 设图G=(V, E)，定义?(G)=min{deg(v), v?V}为G的最小度（类似可以定义 ?(G)=max{deg(v), v ?V}为G的最大度）。若G是简单图，?(G) ? k，T是一棵含k条边的树，则在G中存在与T同构的子图。（提示：对k作归纳。） 证：对 k作归纳。 易知 k=1时结论成立。 设 k=p时结论成立。 当 k=p+1时，
G是简单图，?(G)?p+1。设树T含p+1条边（p+2个顶点），v0是T的一个叶子结点，u是v0的邻接点，其余顶点编号为v1~vp。记e=(u, v0)，T0=T?e，则G和T0符合归纳假设的条件，G中存在与T0同构的子图T0?。将T0? 的p+1个顶点与T0的顶点对应，编号为u?, v1?~vp?。 考察顶点u?，由于deg(u?)?p+1，可见u?至少与除了v1?~vp? 之外的一个点邻接。将该点编号为v0?，记 e?=(u?, v0?)，构造的T?=T0?+e? 与T同