§0 (综述)
§1 (图的基本概念与应用)
§2
(特殊图)
§3 (染色问题) (本页)
§4 (竞赛中的问题)
§3 染色问题
数学竞赛中，经常出现各种各样的染色问题，诸如点染色，边染色，面染色等等，许多染色问题都与图论有密切的关系．实际上，在图论发展史上，“四色猜想”就是一个久负盛名的问题，这个猜想的内容是：任何一个平面地图，至多使用四种颜色染色，就可以把所有相邻（有公共边界）的国家区分开．人们为了证实这一猜想，经过了一百多年的努力，直到 1976 年，才由 Appel，Haken，Koch 等人借助电子计算机经过 1200 个小时，作了近 100 亿个逻辑判定才予以证实．是否能不借助机器证明来解决这一难题，至今仍有人在进行探索．总之，解决“四色问题”的种种努力，大大推动了图论的发展．
下面，给出几个染色体的例子．
例 9 以任意方式对平面上每一点染红色或蓝色．证明一定可以找到无穷多个顶点为同一颜色的三角形．
证 若平面上所有的点颜色相同，则结论显然成立．否则，取两个颜色不同的点
，
及不过此两点的直线 
．
上必有无穷多个红色或蓝色的点．（否则，两种颜色的点都有限，则 
上点有限，引出矛盾），从 
上无穷多个同色点中任取两个，与同色的 
（或 
）组成一个顶点颜色相同的三角形．显然，这样的三角形有无穷多个．
例 10 用任意方式给平面上所有的点染红色或蓝色．求证：一定存在无数多条长为 1 的线段，这些线段的两端颜色相同．
证 用边长为 2 的正方形网划分平面．在每个网格内任取三点，使它们构成边长为 1 的正三角形．这三点中必有两点颜色相同（图 8）．于是每个网格内可得一条长 1 为且两端颜色相同的线段，由于网格的数目无穷多，因此这样的线段有无数多条．
图 8
例 11 在 
的国际象棋盘的 64 个格子中取 16 个格子．证明：如果每一行每一列都恰好取了两个格子，那么一定可以把
8 个红起棋与 8 个蓝棋子放在这些取定的格子里，使得每一行与每一列都恰有一个红棋子与一个蓝棋子．
证 把 16 个格子作为 
图的 16 个顶点，如果两个格子在同一行或同一列，那么就把相应两个顶点之间连上一条边．由已知图
的每个顶点度数都为 2，因此 
是回路或若干回路的并．又由于每行或每列只有两个顶点，因而在每个回路上的边横竖相间，于是每个回路上的边数都是偶数，顶点个数也是偶数．在每个回路上任取一点
，自 
开始给回路的各个顶点交替用红、蓝两色染色，于是相邻顶点（即位于同一行或同一列的顶点）一个染红色，一个染蓝色（图
9），问题得证．
图 9
例 12 五棱柱 
，上、下底面五边形的各边和所有线段 
皆染上红色或绿色，每个三角形如果它的顶点是棱柱的顶点，而且各边皆已染色，则有两边颜色不同．求证，在上、下底的
10 条边是同色的．（ 21 届 IMO，1979 年）
证明 (见相关知识 注3)
例 13 在直角坐标平面里，取 
区域 
，用红蓝两色去染 
（包括边界）的整点．每点染且只染一种颜色，证明不论怎样染色，区域 
总含有这样的矩形，它的顶点为同色的整点，边平行于坐标轴．如果区域是 
的，则存在这样一种染法，使区域 
不含这种矩形（美国数学竞赛题）．
证 为便于叙述，顶点为同色整点而边平行于坐标轴的矩形叫单色矩形．
的每一列上有 7 个整点，染有 2 色，因此至少有 4 点同色．由于调换 
的某两行（两列），
的单色矩形仍为单色矩形．所以不妨假设在 
的第一列上 
，
，
，
这四个点为红色．
如果区域 
的某一列上两个整点为红色，则 
含有单色（红色）矩形．因此可设 
的每一列至多一个红色整点．于是 
的 8 个整点中至少有 6 个为蓝色整点．由于 
只有 4 行，每行只有 2 个整点，于是 
必有两行全为蓝色整点，因此在 
中就有单色（蓝色）矩形（图 11）．
图 11
关于 
区域中不存在单色矩形的例子，留给读者作为练习．