0%

离散数学《图论与代数结构》第7周习题

应该在电脑上写的,但是已经在纸上写完了…鸽了鸽了。

但是这周题挺好的,把最后一题抄上来吧。

12.

设G是每个面都是三角形的平面图,用3种颜色对它的所有结点任意着色。证明:顶点上恰好得到了这3种颜色的面的数目是偶数个。

前排提示:这道题最简单的做法是将相邻同色点缩点。


记C为顶点上恰好得到了这3种颜色的面的数目。不妨设3种颜色为RGB。只需要证,任意调整某一个点的颜色,C的奇偶性不变。若得证,则可将所有点的颜色调整至相同,此时C=0,为偶数,故任意着色后C为偶数,证毕。

对于某个点A考虑,不妨设它原来的颜色是R,我们将其调整为B。考虑A的邻居。

1

A的邻居缺少颜色B或G,则无论A是什么颜色,都对C没有贡献。

2

A的邻居的颜色都不是R,只有BG。从某个邻居开始按顺序写下它们的颜色(要求这个邻居与前一个或后一个邻居的颜色不同),并将极长的相同颜色段缩为一个(因为两个相同颜色的点与A构成的面的颜色数目<3,对答案没有贡献),得到的序列形如BG…BG或GB…GB。颜色不同且序列上相邻的两点与A构成的面,在A改变颜色后会使C-1,由于序列长为偶数,故C的奇偶性不改变。

3

A的邻居中含有3种颜色,将极长的相同颜色段缩为一个,以R为分界点断开,得到的每一段内只有BG交替出现。考虑每一段。

3.1

若段长为奇数,即形如BG…GB或GB…BG,则改变颜色后,会减少偶数个符合条件的面,同时增加0或2个符合条件的面,C的奇偶性不变。

3.2

若段长为偶数,即形如BG…BG或GB…GB,则改变颜色后,会减少奇数个符合条件的面,同时增加1个符合条件的面,C的奇偶性不变。

综上,改变一个点的颜色,C的奇偶性不变。由开始时的论证知,原命题成立。