CSP-S 2023 第一轮 第6题：以下连通无向图中，（）一定可以用不超过两种颜色进行染色。

题目

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

选项

• A. 完全三叉树
• B. 平面图
• C. 边双连通图
• D. 欧拉图

答案

A

题解

答案是 A. 完全三叉树。

图的染色要求：相邻的两个顶点颜色不同。一个无向图能用不超过两种颜色染色，当且仅当它是二分图，也就是不含奇数长度的环。

• A：一定可以。 树没有环。以根节点为第 0 层，偶数层染一种颜色，奇数层染另一种颜色。树的每条边都连接相邻两层，因此不会冲突。每个节点有几个孩子不影响结论。
• B、C、D：都不一定。 用一个三角形就能同时举出反例：它是平面图；删掉任意一条边后仍连通，所以是边双连通图；沿三条边走一圈就是欧拉回路，所以也是欧拉图。但三个顶点两两相邻，必须用 3 种颜色。

记住：树一定能二染色；有奇环的图不能二染色。