NOIP 提高组初赛 · NOIP 2015 提高组初赛试题 第 14 题

对图 $G$ 中各个结点分别指定一种颜色，使相邻结点颜色不同，则称为图 $G$ 的一个正常着色。正常着色图 $G$ 所必需的最少颜色数，称为 $G$ 的色数。那么下图的色数是（ ）。 

正常着色：相邻结点颜色不同。该图所需的最少颜色数为 3（据图分析：图中有奇环，至少需 3 色）。

色数 = 最少着色数。图中含三角形（奇环）时至少 3 色；若图是二分图则 2 色足够。

考点概念：图的色数

正常着色：相邻结点颜色不同。 色数：正常着色所需的最少颜色数。

• 二分图（无奇环）：色数为 2
• 含奇环的图：色数 ≥ 3

本题图形含奇数环，最少需要 3 种颜色，选 A。