第 68 讲 图论问题(二)本讲主要内容：本讲将继续研究用图来解决问题的方法．偶图 取图 G＝(V，E)，如果 V＝X∪Y，X∩Y＝，其中 X＝{x1，x2，…，xn}，Y＝{y1，y2，…，ym}，且 xi与 xj(1≤i＜j≤n)，ys与 yt (1≤s＜t≤m)均互不相邻，则称 G 为偶图．色数：将图 G 的顶点涂上颜色，如果至少要 k 种颜色才能使任意两个相邻的顶点颜色不同，则称 G 的色数为 k．显然，偶图的色数≤2．即偶图色数不超过 2．A 类例题 例 1 在空间中给定 2n 个不同的点 A1，A2，…，A2n，n＞1，其中任意三点不共线．设 M 是 n2+1条以给定的点为端点的线段的集合．⑴证明：存在一个三角形，其顶点为给定的点，其边都属于M．⑵证明：若集合 M 的元素不超过 n2个，则这样的三角形可能不存在．(1973 年奥地利数学竞赛)分析 可以从简单的情况开始试验，发现规律再证明．从 K4(4 阶完全图，见 67 讲)共有多少条线及多少个三角形、擦去 1 条线去掉几个三角形入手得出结论，对于 K5、K6也能用此法得到结论，但对于 p＞6，Kp难用此法，如何过渡到一般情况？可以用数学归纳法．证明：n＝2 时，在 4 个点间连了 5 条线，由于 4 阶完全图在 4 个点间共可连出 6 条线，这 6条线连出了 4 个以此 4 点中的某 3 点为顶点的三角形．而每条线的两个端点与(除这条线的两个端点外的)另两个顶点可以连出共 2 个三角形，故去掉任何一条边都使连出三角形数减少 2，于是在 4 个点间连 5 条线必连出了以此 4点中的 3 点为顶点的三角形．设 n＝k 时，2k 个点间连有 k2＋1 条线时，必有三角形出现．则当 n＝k＋1 时 ，2(k＋1)个点间连了(k＋1)2＋1 条线．此时，任取两个相邻的顶点 v1，v2，如果在其余的顶点中有某个顶点与 v1，v2都连了线，例如 v3与 v1，v2都连了线(图 4(1))，则出现了三角形．如果其余所有的点与此二点都至多连出 1 条线(图 4(2))，则去掉点 v1，v2及与这两点相邻的边，此时，余下 2k 个点，至多去掉了 2k＋1 条边，余下至少(k＋1)2＋1－(2k＋1)＝k2＋1 条边，由归纳假设知，其中必有三角形．综上可知，命题成立．说明 若 2n 个点间连了 n2条边，可以把这 2n 个点分成两组，每组 n 个点，规定同组的点间都不连线，不同组的任何两点都连 1 条线，这样得到了一个完全偶图 Kn，n，此时共计连了 n2条线，但任取三点，必有两点在同一组，它们之间没有连线，于是不出现...
