大门|大门-CS-2009 |问题2

不包含奇数圈的n-顶点单连通图的色数是多少？假设n>=2。 （A） 2. （B） 3. （C） n-1 （D） N 答复: （A） 说明： 图的色数是为图的顶点着色所需的最小颜色数，这样相邻的两个顶点就不会共享相同的颜色。这类问题可以通过用不同的n值替换来解决。

1） n=2 这个简单的图形可以用两种颜色着色。

2） n=3

这里，在这个图中，让我们假设顶点A用C1着色，顶点B，C可以用颜色C2着色=>色数是2，同样，你可以用其他值检查，色数等于2

这个解决方案由 阿尼尔·赛克里希纳·德瓦拉塞蒂

//没有奇数圈的简单图是二部图，二部图可以用两种颜色着色（参见 这 ) 这个问题的小测验