第一章习题 1.对任何简单图G,(1)证明:E(G)≤ 2:(2)(G) U(U-1) 2当且仅当G≡K, 2.证明:(1)E(Kn)=m;(2)若G是完全二部图,则E(G)≤0 3.图G有21条边,12个3度顶点,其余顶点的度均为2,求图G的阶数 4.证明:任何简单图必有至少两个顶点具有相等的度。 5.设G是简单图,求G的所有不同的生成子图的个数(包括G本身和空图)。 6.证明:任何图中,奇度顶点的个数总是偶数(包括0)。并由此证明:在任一次聚会上握过奇数 次手的人必为偶数个。 7.证明或反证:如果u和γ是图G中仅有的具有奇数度的顶点,则G包含一条u,v路 8.证明:若U≥4且E=v+1,则存在v∈(G)使得d(v)≥3。由此证明:n个球队比赛(n≥4) 已赛完n+1场,则必定有一个球队已参加过至少3场比赛 9.在一个运动联盟中,将所有运动队组织成两个赛区,每个赛区有13个队,能否恰当安排比赛使 得每个队在其所在赛区中进行9场比赛而与另一个赛区中的运动队进行4场比赛? 10.在平面上有n个点S={x,x2,…xn},其中任两个点之间的距离至少是1。证明在这n个点中 距离为1的点对数不超过3n。 11.某次会议有n人参加,其中有些人互相认识,但每两个互相认识的人,都没有共同的熟人,每 两个互不认识的人都恰好有两个共同的熟人。证明每一个参加者都有同样数目的熟人 12.在一个化学实验室里,有n个药箱,其中每两个不同的药箱恰有一种相同的化学品,而且每种 化学品恰好在两个药箱中出现,问:(1)每个药箱有几种化学品?(2)这n个药箱中共有几种 不同的化学品? 13.在一次舞会中,A、B两国留学生各n(m>2)人,A国每个学生都与B国一些(不是所有)学生跳 过舞,B国每个学生至少与A国一个学生跳过舞。证明一定可以找到A国两个学生a1,a2及B 国两个学生b1,b2,使得a1和b,a2和b2跳过舞,而a1和b2,a2和b没有跳过舞。 14.证明:d≤二≤Δ,(其中二称为顶点平均度)。 15.令G是至少有两个顶点的图。证明或反证:(1)删除一个度为△(G)的顶点不会增加顶点的平均 度;(2)删除一个度为(G)的顶点不会减小顶点的平均度 16令G是一个顶点平均度为a=2的无圈图。(1)证明:G-x的顶点平均度至少为a当且仅当 d(x)≤。(2)利用(1)的结果给出一个算法来证明:如果a>0,则G有一个最小度大于的 子图第一章习题 1. 对任何简单图 G，(1) 证明： ( 1) ( ) 2 G υ υ ε − ≤ ；(2) ( 1) ( ) 2 G υ υ ε − = 当且仅当G K≅ ν 。 2. 证明：(1) , ( ) K mn m n ε = ；(2) 若 G 是完全二部图，则 2 ( ) 4 G υ ε ≤ 。 3. 图 G 有 21 条边，12 个 3 度顶点，其余顶点的度均为 2，求图 G 的阶数。 4. 证明：任何简单图必有至少两个顶点具有相等的度。 5. 设 G 是简单图，求 G 的所有不同的生成子图的个数（包括 G 本身和空图）。 6. 证明：任何图中，奇度顶点的个数总是偶数（包括 0）。并由此证明：在任一次聚会上握过奇数 次手的人必为偶数个。 7. 证明或反证：如果 u 和 v 是图 G 中仅有的具有奇数度的顶点，则 G 包含一条 u, v 路。 8. 证明：若υ ≥ 4 且ε =ν + 1，则存在v ∈V (G) 使得d(v) ≥ 3 。由此证明：n 个球队比赛（ n ≥ 4 ）， 已赛完 n+1 场，则必定有一个球队已参加过至少 3 场比赛。 9. 在一个运动联盟中，将所有运动队组织成两个赛区，每个赛区有 13 个队，能否恰当安排比赛使 得每个队在其所在赛区中进行 9 场比赛而与另一个赛区中的运动队进行 4 场比赛？ 10. 在平面上有 n 个点 1 2 {, , , }n S xx x = ⋅⋅⋅ ，其中任两个点之间的距离至少是 1。证明在这 n 个点中， 距离为 1 的点对数不超过 3n。 11. 某次会议有 n 人参加，其中有些人互相认识，但每两个互相认识的人，都没有共同的熟人，每 两个互不认识的人都恰好有两个共同的熟人。证明每一个参加者都有同样数目的熟人。 12. 在一个化学实验室里，有 n 个药箱，其中每两个不同的药箱恰有一种相同的化学品，而且每种 化学品恰好在两个药箱中出现，问：（1）每个药箱有几种化学品？（2）这 n 个药箱中共有几种 不同的化学品？ 13. 在一次舞会中，A、B 两国留学生各 n n( 2) > 人，A 国每个学生都与 B 国一些(不是所有)学生跳 过舞，B 国每个学生至少与 A 国一个学生跳过舞。证明一定可以找到 A 国两个学生 1 2 a a, 及 B 国两个学生 1 2 b b, ，使得 1 a 和 1 2 b a , 和 2 b 跳过舞，而 1 a 和 2 2 b a , 和 1 b 没有跳过舞。 14. 证明： 2ε δ υ ≤ ≤Δ ，（其中 2ε υ 称为顶点平均度）。 15. 令 G 是至少有两个顶点的图。证明或反证：(1) 删除一个度为 Δ( ) G 的顶点不会增加顶点的平均 度；(2) 删除一个度为δ ( ) G 的顶点不会减小顶点的平均度。 16. 令 G 是一个顶点平均度为 2 a ε υ = 的无圈图。(1) 证明：G x − 的顶点平均度至少为 a 当且仅当 ( ) 2 a d x ≤ 。(2) 利用(1)的结果给出一个算法来证明：如果 a > 0 ，则 G 有一个最小度大于 2 a 的 子图