（2） 若对于平面图，且不含三角形，则它的任何面f的次数均大于等于4，又 故得4??2?，???d(f)?2?f?F
?2，由欧拉公式
?2?u???u? 2???u????2,??2u?4
即不含三角形的平面图有??2u?4
因此对不含三角形的图G有
Q(G)????? 证毕
?2u?4??定理 7·10 Q(K9)?Q(K10)?3，且对任何Kn(n?3)都有 ?(Kn)???6证 对于完备图Kn，有 ??12n(n?1)
13n?6?n?7? ??令 ??1?
因n?3,则0???1，于是由定理7·9有 ?1?n(n?1)?2? ?(Kn)???
3n?6???? ?? ?1??3n?6??6n?12 ???6
?n?7?? ??n(n?1)1? 证毕。
第八章 图的着色
k
定义 8·1 （1）图G的一个k边着色是指对E(G)的一个划分L?(E1,E2,?,Ek),E
(G)??E,Eii?1i?Ej??,i?j,其中Ei表示着i色的边的集合，(i?1,2,?,k)。若每个Ei都是G的匹配，则称L是一个适当k边上色。
（2）若G有一个适当k边上色，则称G是可k边上色的。
（3）若G是可k边上色，而不是可(k?1)边上色，则称k是G的边色数，记为
X?(G)?k。
（4）若X?(G)?k，则称G是k的边色图。
引理 8·1·1 若连通图G不是奇圈，则G有一个2边上色，使得该二色附着于每个次数至少为2的顶点。（若与u关联的边中有一边是色i，则称色i附着于顶点u）。
证 设G是欧拉图；若G是偶圈，命题显然成立。若G不是偶圈，则G至少有一个顶点u0,d(u0)?4.设u0e1u1e2u2?e?u0是G的一个欧拉巡回，令
E1??eii为奇数? E2?eii为偶数??
则L?(E1,E2)即为满足要求的2边着色。
若G不是欧拉图，加入一个新顶点u0，并在u0与G的每个奇次顶点之间各连一条边，
****
得到图G，G是欧拉图，设C?u0e1u1e2u2?e?，u0是G的一个欧拉巡回，令
E1??eii为奇数? E2?eii为偶数??
则L??E1?E(G),E2?E(G)?即为满足要求的2边着色。
定义 8·2 （1）设L是G的一个k边上色，把附着于顶点u的颜色数目记为c(u)。 （2）若有一个k边着色L?，使得 则称L?是L的改进。
（3）不能再改进的k边着色，称为G的一个最佳k边着色。
引理 8·1·2 设L?(E1,E2,?Ek）是G的一个最佳k边上色，若G有一顶点u和色i,j,使得i不附着u而j却两次附着u，则G?Ei?Ej?含u的连通片是一个奇圈。
?c?(u)??c(u)
u?V(G)u?V(G)证 设u是满足引理条件的一个顶点，用H表示G?Ei?Ej?含u的那一个连通片。假定H不是奇圈，由引理8·1·1，H有一个2边上色，使该二色附着于H每个次数至少是2的顶点上。我们用i色和j色依引理8·1·1的方法给H的边重新上色，而G的其它边
?,?Ek?）中，i,j两色都附着于u，因此保持原色。此新的k边着色L??(E1?,E2c?(u)?c(u)?1。而对??u,c?(?)?c(?)，于是
?c?(u)??c(u)
u?V(G)u?V(G)故L?是L的改进，这与L是最佳K边着色矛盾。因此H必定是奇圈。证毕。 定理8·1 如果G是二部图，则X?(G)??
证 若X?(G)??，设L?(E1,E2,?E?）是G的一个最佳?边上色，设u是满足
c(u)?d(u)的顶点，则显然u满足引理8·1·2的条件，因此，G含有一个奇圈，与G是
二部图矛盾，故X?(G)??,又X?(G)??,因此
X?(G)?? 证毕。
定理 8·2 （Vizing,1964） 设G是简单图，则??X?(G)???1
证 设G是简单图，但X?(G)???1,L?(E1,E2,?,E??1)是G的一个最佳??1边着色，设u是满足c(u)?d(u)的一个顶点，则存在色i0和i1使得i0不附着u而i1却两次附着u。设u?和u?1是色i1（图8-3）。因为d(?1)???1，故有某色i2不附着?1，但i2必定附着u，否则用i2给u?1重新上色将得到L的一个改进，这与L是最佳??1边着色矛盾。于是设u?2是色i2。又d(?2)???1，故有某色i3不附着?2，但i3必定附着u，否则用i2给u?1着色，用i3对u?2上色，会得到L的一个改进。于是有某边u?3有色i3。继续这个过程，我们将得到一个顶点序列?1,?2,?和一个色序列i1,i2,?使得
?）（1）u?j有色ij(j?1,2，
（2）色ij?1不附着于?j(j?1,2,?)
由于与u关联的边是有限的，故存在一个最小的正整数l，使得对某个k?l有 （3）il?1?ik(k?l)
现在我们对G的边重新上色如下：对于l?j?k?1，用ij?1给边u?j上色，而产生一?,?E???1）个新的??1边上色L??(E1?,E2见图（8-4）。
显然，对于G的每个顶点，都有c?(?)?c(?)，如果存在一个顶点有严格不等式成立，则与L是最佳上色矛盾，故对G的每个顶点都有c?(?)?c(?)，故L?也是G的一个最佳
??1边上色。由引理8·1·2，GEi?0?E?j0含u的连通片H?是奇圈。
??现在我们再用色ij?1给边u?j(k?j?l?1)重新着色，用ik给边u?1，又得到G的一个??,?E????1）最佳??1边上色L???(E1??,E2见图（8-5）。
显然对G的每个顶点，都有c??(?)?c(?)，L??也是G的一个最佳??1边上色，于是
GEi?0??Ei?k?含u的连通片H??也是一个奇圈。然而H?中i0附着在?k上，但在H??中
???k?H??，且i0仍应附着在?k上，故在H??中?k的附着数是1，这不可能，因为对一个最
佳上色来说，每个奇圈上，最多只有一个顶点附着数是1。证毕。
定义8·3 设D?V(G)，若任何顶点u?V(G)，或者u?D，或者u与D内某顶点相邻，则称D为G的一个支配集。若支配集D的任何真子集皆非非支配集，则称D为极小支配集。若D0是一个支配集，但无任何支配集D1，使得D1?D0，则称D0是最小支配集，记?(G)?D0，称?(G)为G的支配数。
定理8·4 G中无零次顶点，则存在一个支配集D，使得D?V(G)?D也是一个支配集。
证 不妨设G连通，T是G的生成树，任取?0?V(G)，令
???V(G),dT(?0,?)?0(mod2)? D?? D????V(G),d?(?0,?)?1(mod2) 则D?V(G)?D，且D与D都是支配集。证毕。
定理 8·4 G中无零次顶点，D1为极小支配集，则D1?V(G)?D1也是一个支配集。 证 若有一顶点?0?D1，而D1中没有使?0u?E(G)的顶点u，则D1??0仍是一支配集，与D1为极小支配集矛盾，故D也是支配集。证毕。
??定义 8·4 I?V(G),I中任二顶点均不相邻，则称I为图G的一个独立集，任取u?I,I??u?不是独立集，则称I是极大独立集；G中无独立集I1，使得I1?I，则称I是G的最大独立集，此时，记?(G)?I,?(G)称为G的独立数。
定理 8·5 一个独力集是极大独力集，并且仅当它是支配集。
证 设I是独力集，且是极大独力集，则对任何??I，都存在I中某顶点与u相邻。从而I是支配集。
反之，若I是独力集，又是支配集，则对任何??I，都存在I中某顶点与?相邻，故I??u?不是独力集，从而I是极大独力集。证毕。
定理 8·6 I是独力集，当且仅当V?I是点覆盖。
证 设I是独立集，就不存在两个端点都在I的边，即G的每一边至少有一端点在V?I，故V?I是G的点覆盖。
反之，设V?I是G的点覆盖，则G的每一边至少有一端点在V?I，G不存在两个端点都在I中的边，故I是G的独力集。证毕。
推论 8·6·1 K是极小点覆盖，当且仅当V?K是极大独力集。 推论 8·6·2 ?(G)??(G)??
证 设I是独立最大集，I??(G)；设K是最小覆盖集，K??(G)，由定理8·6，V?I是覆盖集，得
???(G)?V?I??(G) （1） 而V?K是独力集，因此
???(G)?V?K??(G) （2） 由（1），（2）得
?(G)??(G)?? ?(G)??(G)??
故 ?(G)??(G)?? 证毕。 定理8·7 极大独力集必为极小支配集。
证 不妨设?(G)?0,设I为极大独力集，则对任何u?I,u与I中一顶点相邻，因此I是支配集，又任取u?I,u与I??中的顶点不相邻，可见I是最小支配集。证毕。
定义8·5 设M?E(G),M中任二边不相邻，则称M是一个边独立集；G中最大边独立集的边数，称为G的边独立数，记为??(G)。