CSP-S 提高级 · CSP 2023 提高级第一轮 第 6 题

以下连通无向图中，（）一定可以用不超过两种颜色进行染色

这题其实就在考二分图的定义。看到'不超过两种颜色'，脑子里立刻要跳出'无奇环'这几个字。然后逐个选项想：哪些图天生就没有奇环？树肯定没有环，那它一定没有奇环；平面图、边双连通、欧拉图虽然性质很好，但都可能藏着三角形这种奇环，所以不能选。

最容易掉进'平面图'这个坑。很多学生觉得平面图能在纸上画出来不交叉，那就很'干净'，误以为它一定没有奇环。其实平面图只是拓扑性质，完全可能包含三角形（比如K3就是平面图），一旦有奇环，2色就染不上了。另一个坑是混淆'边双连通'和'无奇环'的概念，以为去掉一条边还连通就代表没有奇环，这也是错的。

考点定位 这道题的核心就是图论里的二分图判定：一个图能用不超过两种颜色染色，等价于它是二分图，等价于图中不含奇环（奇数长度的环）。拿到题先想这个转化链条，后面所有选项的判断都绕不开'有没有奇环'这一条线。

逐个拆解选项 A 完全三叉树：树这种结构天生就没有环，既然连环都没有，更别提奇环了。从根开始一层层交替染色（根红、子蓝、孙红……），永远不会出现同色相邻，所以它一定是二分图，2 色染色毫无问题。 B 平面图：平面图只保证能在平面上画得不交叉，跟有没有奇环没关系。举个最简单的反例：一个三角形（K3）就是平面图，但它有 3 个顶点的奇环，必须用 3 种颜色才能染好，所以平面图不一定能 2 色。 C 边双连通图：这个概念的意思是去掉任意一条边图依然连通，它强调的是边的冗余性，完全不涉及环的奇偶性。同样可以构造出含奇环的边双连通图，比如一个三角形加一条弦，去掉任意一条边还是连通的，但奇环还在，2 色不行。 D 欧拉图：欧拉图要求所有顶点度数为偶数，这跟奇环的存在与否也是两码事。存在欧拉图里完全可能有奇环，只要那个奇环的每个顶点度数都是偶数就行（比如三角形每个顶点度数 2，确实是欧拉图），所以欧拉图也不一定 2 色。

避坑总结 学生最容易错选 B，因为'平面图'听起来很'优雅'，容易误以为它天然没有奇环。要记住：2 色 ⇔ 无奇环 ⇔ 二分图，这三者是铁律，跟图能不能画成平面毫无关系。只要脑子里死死抓住'无奇环'这个条件，就能一眼排除 B、C、D。

考频与趋势 图的基本概念是高频考点，题库里一共考过 281 题，覆盖 11 个级别，从 2007 年一直延续到 2026 年，2023 年单年就有 36 题，2024 年更是飙升到 61 题，2025 年 58 题，2026 年 71 题，呈现明显的上升趋势。其中 CSP 提高级就考了 13 题，说明这类概念辨析在提高级里很常见。相比之下，树形结构只考了 26 题，虽然近年也有增长（2026 年 8 题），但总量远不及图的基本概念。BFS 考了 35 题，分布相对均匀，没有特别集中的年份。

预测 基于图的基本概念近年持续高热（2024-2026 连续三年都在 55 题以上），且提高级里专门考了 13 题，未来两三年这类'概念辨析 + 反例构造'的单选题大概率还会是命题人的宠儿，可能会换个马甲考，比如给一个具体图让判断能否 2 色，或者给一个性质问是否蕴含无奇环。树形结构的考频虽然低，但在提高级里已经出现过 6 次（2023 年 6 题），说明树的相关性质（比如树一定是二分图）也可能被单独拎出来考，不过从总量看，图的基本概念仍是绝对主力。