引理6.1.2 设 C =（E1 ，。。。，Ek）为G的一个最优k-边着色。若G中有一顶点u及色i与j，使i不表现于u，而j在u上至少表现2次。则G[Ei ? Ej ]中含u的分支是一奇圈。
证明：令H为G[Ei ? Ej ]中含u的分支。假设H不是奇圈，由引理6.1.1.，H有一2-边着色，使该二色表现于H的每个度?2顶点上。以这方式，用色i与j对H重新边着色，得G的一个新的k-边着色C?。显然， c?(u) = c(u) + 1 c(v) ? c(v) ? v?u ?
?c'(v)??c(v) 这与C为最优矛盾。
v?Vv?V?
定理6.1 设G为偶图，则?? = ? 。
证明：反证，假设?? > ? 。令C为G的一个最优?-边着色，而u ? V为使 c(u) < d(u)
的顶点。于是u满足引理6.1.2.条件，从而G包含奇圈。这与定理1.2 相矛盾。 ?
另一证法（Wilson）对? 进行归纳。当 ? = 1 时显然成立。假设对 ? < 1 都成立，而 ?(G)= k 。任取G的一边 e = uv ，考虑
G? = G - e 。
由归纳假设，G? 有一 ?(G?)-正常边着色 C?={E1?,...,E?(G?)}。
若 ?(G?) < ?(G)，则G显然有?(G)-正常边着色，证完； 否则，?(G?) = ?(G)。令Au与Av各表示C?中不表现于u与v的色集。由于在G?中u与v都不是其最大度顶点，从而有
Au ，Av ? ? 。
① 当 Au ? Av ? ? 时：将Au ? Av 之一色着在边e上，即得G的?(G)-正常边着色。
② Au ? Av = ? 时：任取色i ? Au 及色j ? Av 。令H为G[Ei? ? Ej?] 中含u的分 支。易见，H是一条路，由色i与色j边交替组成。因此，v一定不在H上（不然，H的第一条边有色j，最后一边有i ，从而其长为偶数。这导致G中含一奇圈H + e，矛盾。）对换H上的色i与j，得G?的另一正常 ?(G?)-边着色，其中在u与v上色j都不表现。 再将色j着在e上，即得G的正常 ?(G)-边着色 。 ?
习题
6.1.1 找出一适当的边着色以证明??(Km,n) = ?(Km,n)。
6.1.2 (a) 证明：任一偶图G都有一?-正则偶母图。 （不一定为生成母图！） (b) 利用(a)给出定理6.1 的另一证明。 6.1.3 叙述求偶图G的正常?-边着色的好算法。
*
6.1.4 证明：若偶图G有 ? > 0 ，则G有一?-边着色，使所有? 种色在每一顶点上都表现。
Vizing定理
定理6.2 (Vizing,1964) 对简单图G有 ?? = ? 或 ? + 1 。 证明：（Bollobas）不妨设G中 除uv1外 都已用色 1,2,??,? +1
进行了正常边着色。注意到，G的每个顶点上都至少有一色未表现。令u，v1 各有色i0，i1 未表现。我们可逐步找到不同的色、边序列：
i0 ， i1 ， i2 ，??，ij ，?? ； uv1 ，uv2 ，??，uvj ，?? 。 其中， 色ij 是顶点 vj 上未表现的（任意取定的）一色；
31
边uvj 有色ij-1 。 j=2，3，?? 。
显然，上述过程至多进行到某l（ ? ?）次而停止（无法继续满足上述条件）。 这时只有两种可能： (A) 色il 未表现于顶点u上（即没有一条u的关联vk+1(ik+1)边uvk有色il ）：重新进行边着色如下
vk(ik)
ik-1ik uvj 改着色ij 1 ? j ? l-1
并抹去边uvl 上的色 il-1 。 i2u(i0)得G中除uvl 外的正常（? +1）边着色。其中u与vl
v3(i3)i1上色il 同时不表现。将uvl 改着色il 即得G的正常（? +1）
il-1no边着色。 vl(il)v2(i2)(B) il = ik 某 1 ? k ? l-1 ： 重新进行边着色如下
将uvj 改着色ij 1 ? v1(i1)j ? k
v(i)表示v上色i未表现 并抹去边uvk+1 上的色 ik 。
易见， H = G[EE] 的每个分支是路或圈，由
i0?ik色i0与ik的边交错组成，且
u，vk+1，vl 在H中的度? 1。
从而，该三顶点不可能同时在H的一分支中。这时只有二可能情形： ① u 与vk+1不在H的同一分支中：将H的含vk+1分支中
vk+1(ik+1)的色i0 与ik对换，得G 的除uvk+1外的正常（? +1）-边着色，
vk(ik)其中u与vk+1上色i0都未表现。从而，G有一正常（? +1）-边
no着色。
ik② u与vl不在H的同一分支中： 再继续调整边着色如
i3u(i0)下，
v3(i3)i 将uvj 改着色ij 并抹去边uvl 上的色 （il-1 ） 2il-1 k+1 ? j ? l-1 。 i1vl(il)v2(i2)易见，上述更动并未涉及色i0与ik ，因此H 保持不变。
将H中含u分支的色i0 与ik对换，得G 的除uvl外的正常（?
v1(i1)+1）-边着色，其中u与vl上色i0都未表现。从而，G有一正常 （? +1）-边着色。 ?
注1 对一般图有 Vizing定理 设G为无环图，则 ? ? ?? ? ? + ? ，其中?是G的重数（连接G中每一顶点对上的最大边数） 。
注2 NP-complete prob。已给简单图G，是否有?? = ? ？
注3 “2-边连通、3-正则、简单、平面图都有?? = 3” ? “4-色猜想成立”。
习题
6.2.1* 找出适当的边着色以证明??(K2N-1) = ??(K2N) = 2n-1 。 6.2.2 ? 为奇数的非空正则简单图G有 ?? = ? + 1 。 6.2.3(a) 设简单图G中? = 2n+1且? >n ? ，则?? = ? +1 ； (b) 利用(a)证明： ① 若G是从有偶数个顶点的简单图中剖分一条边所得的图，则?? = ? +1 ； ② 若G是从有奇数个顶点的简单k正则图中删去少于k/2条边所得的图，则 ?? = ? + 1 。
6.2.4(a) 证明： 任一无环图G都有?-正则无环母图。
(b) 利用(a)及习题5.2.3(b)证明：若G 是无环图且? 是偶数，则?? ? 3? /2。
6.2.5 称G为唯一k-边可着色的，如果G的任意两个k-边着色都导致E有相同的划分。证明：每个唯一3-边可着色的3-正则图都是Hamilton 图 。
6.2.6 简单图的积图是指顶点集为V(G)×V(H)的简单图G×H，其中
(u,v)与(u?,v?)相邻 ? u = u?且v?? ? E(H)； 或v = v?且uu? ? E(G) (a) 利用Vizing定理证明：??(G×K2）= ?(G×K2) 。
32
(b) 试证：若H是非平凡的，且??(H) = ?(H)，则??(G×H) = ?(G×H)。 6.2.7 叙述求简单图G的正常(?+1)-边着色的好算法。
*
6.2.8 证明：? ≥2的简单图G有一(?-1)-边着色，使得所有?-1 种色在每个顶点上都表现。
排课表问题
问题 m位教师X1，??，Xm和n个班级Y1 ，??，Yn ，其中教师Xi要给班级Yj上pij节课。欲在最少节次p内排完所有的课。
? 将偶图G = (X,Y,E) (?X?=m ，?Y?=n)的边集E划分成互不相交的p个匹配(E1，??，Ep)
? 求偶图G的??（=? =p）-边着色。 由习题6.1.4知，上述问题有好算法。
当上述问题中若教室数有限时（ 教室数≥maxEi ），若要在p（? ? ）节内排完全部l（= ?E?）
1?i?p节课，所需教室数c ? ?? 。
问题 能否适当排课，使全部l节课在p（? ? ）节内排完，且每节课所用 教室数? ?? ？（∴???Ei??? ? 1? i ? p ）
引理6.3 设M，N为G的二不相交匹配，且?M?>?N?，则存在G的二不相交匹配M?，N?使?M?? =?M?-1 ，?N?? = ?N?+1 ，且M??N? = M?N 。
证明：令H = G[M?N]，则H的每个分支为一路或圈，由M及N的边交错组成。且由于?M?>?N? ，存在H的一个分支，它是路P， 起、止于M 边。因此
M? = M ? E(P) 及 N? = N ? E(P) 即为所求。
定理6.3 设G为偶图，p ? ? ，则存在G的p个互不相交的匹配使 E = M1 ? ??? Mp 。
且 ???Mi??? 1 ? i ? p 。
证明：由定理6.1, E可划分为 ? 个互不相交的匹配 M1?，??，M?? 。
因此，对p ? ? ，G有p个互不相交的匹配 M1?，??，M??，??，Mp?。 （令Mi?= ? 当i > p) 使E = M1?? ??? Mp? 。对边数差 > 1的两个匹配，重复使用引理6.3，最后可得所求的匹配M1，??，Mp 。 ?
注 在实际应用中，教师和班级往往会提出一些，例如所上节次，的要求，问题变得很复杂。Even，Itai & Shmir（1976）证明：在教师和班级提出条件时，判定课表的存在性问题是个NP-complete问题。甚至当G为简单偶图，且学生不提出要求的情况下，也是如此。
?l??p??l??p??l??p??l??p?????p?????p? 33
独立集和团 独立集
定理7.1 S为图G的独立集 ? V\\S 为G的覆盖。 证明：S为独立集 ? 不存在两端全在S中的边 ? G的每边至少有一端在V\\S 中 ? V\\S为G 的覆盖。 #
S ? V为G的 团（clique） ? G[S]为一完全图。
独立数（independent number）??G? ? 最大独立集的元素个数。 覆盖数（coering number）??G? ? G的最小覆盖的元素个数。
推论7.1 ????? 。
证明：设S为G的最大独立集，则V\\S为其覆盖，因此 ? ? |V\\S |= ? - ? 。
又，设K为G的最小覆盖，则V\\K为其独立集，因此
? ? |V\\K| = ? - ? 。 ∴ ????? 。 #
注 由上述证明知 S为G的最大独立集 ? V\\S为G的最小覆盖 。
顶点着色 色数
正常（顶点）着色（proper （vertex） coluring） ? 每边两端不同色。 k-（顶点）着色（k-（Vertex）colouring） ? k种色在V(G)上的一种分配，且任二相邻（的不同）顶点不同色。 ? V的一个k-划分（V1，??，Vk）使每个Vi（可为?）都是G的一个 独立集。
k-（顶点）可着色（k-（vertex） colourable） ? G有一k-着色。 显然， G为k-可着色 ? G的基础简单图为k-可着色。 由此，我们约定 本章只讨论简单图。
例。 G为1-可着色的 ? G 为一空图。 G为k-可着色的 ? G 为k-部图。
G为k-可着色的 ? G为j-可着色的（k ? j）。 色数（chromatic number） ?(G) = { k ? G为k-可着色的} 。 G为k-色图 ? ?(G) = k。
G为临界的（crtical） ? ?(H) < ?(G) ? H ? G 。
34
? G连通且满足 ?(G-e) < ?(G) ? e ? E(G) 。 G为k-临界的 ? G为临界图，且 ?(G) = k。 显然，G为k-色图 ? G包含一k-临界子图。 例。1-临界图 ? K1 （唯一）。 2-临界图 ? K2 （唯一）。 3-临界图 ? 奇圈 。 4-临界图 例如：K4 ，Grotzsch图等。 注意 一图G的临界图不一定是它的导出子图。
定理8.1 G为k-临界图 ? ? ? k - 1 。 证明：反证，假设 ? < k-1 。取v ? V使d(v) = ? 。因G 为k-临界图的，G-v必是（k-1）-可着色的。令
Grotzsch图 （ V1，??，Vk-1） 为G-v 的(k-1)-着色。由于d(v) = ? < k-1，v一定与某一Vj中所有顶点都不相邻。从而
（ V1，??，Vj?{v}，??，Vk-1） 是G的(k-1)-着色，于是?(G) ? k - 1 ，矛盾。 #
推论8.1.1 ?(G) = k ? G中至少有k个度 ? k-1 的顶点。 证明：令H为G的k-临界子图。由定理8.1知 dH(v) ? ?(H) ? k-1 ? v ? V(H) 。 ∴ dG(v) ? dH(v) ? k-1 ? v ? V(H) 。 又因H为k-色的，必有 |V(H)| ? k 。 #
推论8.1.2 对任一图G都有 ? ? ? + 1 。
证明：由推论8.1.1知 ? ? ? - 1 。 #
令S为连通图G的一个点割。 V1，??，Vn为G - S 的各分支的顶点集。称 Gi = G[Vi?S]
为G的S分支。称G1，??，Gn上的各个着色在S上是一致的，当且仅当在各个着色中S中每顶点都被着以相同的色。
定理8.2 临界图的任一点割都不是团。
证明：反证，假设k-临界图G有一点割S是团。令G1，??，Gn是G的S分支。因G为k-临界的，每个Gi都必是（k-1）-可着色的。但S为团，每个Gi的任一（k-1）-着色都导致S中所有顶点彼此不同色。从而一定存在G1，??，Gn在S上一致的（k-1）-着色。这些着色一起构成G的一个（k-1）-着色，矛盾。 #
推论8.2 每一临界图是一个块。
证明：若v是一割点，则{v}是一个点割，且是团。故临界图不含割点，因而是个块。#
注 NP-complete prob. ： 对任给图G及正整数k ? |V| ，G是否为k-可着色的？ 从而，求任给图G的色数是个NP-hard prob. 。
贪心（greedy）着色法 ：用色1，2，? 逐步（按某一 顶点排序）一个个顶点进行着色，每次选用尽可能小的颜色进行着色。
例如，对任给图G，按任一顺序进行贪心着色，易见，至多用了? + 1 个色，从而得到了推论8.1.2另一证明。
显然，贪心着色法所用的颜色数完全取决于着色的顺序，即顶点的一个排序。假如我们事先知道图G的一个?-着色为
C = （E1，E2，??，E? ） 。
按E1，E2，??，E?任作一顶点排序（同一色集Ei内随意排序），按此顺序进行贪心着色，易见，一定恰好用了? 个色。因此，设法构想一适当的顶点排序进行贪心着色，往往可能得到关于着色的一个较好结果（如Brooks定理之证明）。下面是这方面的一些结果：
35