求不含K₅子图的最小顶点数5-色图

首先咱们明确问题的核心：要找顶点数最少的图，得同时满足两个关键条件：

• 它的色数至少为5（就是说必须用5种颜色才能给所有顶点着色，保证相邻顶点颜色不同）
• 图里绝对不能有5阶完全子图（也就是K₅，5个顶点两两相连的结构）

直接结论：最小顶点数是6 #

咱们可以构造出一个6顶点的图满足所有要求，具体方式很简单：

• 先拿一个4阶完全子图K₄（4个顶点，每两个之间都有边）
• 再添2个新顶点，让每个新顶点都和K₄的4个顶点连边，但这两个新顶点之间不连边

咱们来验证一下这个图的性质：

• 不含K₅：随便挑5个顶点，要么是K₄的4个顶点加1个新顶点（新顶点只和K₄的顶点相连，和其他新顶点没边，凑不出5个两两相连的顶点）；要么是2个新顶点加3个K₄顶点（两个新顶点之间没连接，自然也成不了K₅）
• 色数为5：K₄的4个顶点两两相连，必须用4种不同的颜色；每个新顶点都和K₄的所有顶点相连，没法用那4种颜色，只能用第5种；而且两个新顶点之间没边，共用第5种颜色就行，所以整个图的色数正好是5，完全满足“至少用5种颜色”的要求

至于5个顶点的情况，根本不可能满足条件——因为5个顶点的图如果色数是5，那它本身就是K₅，直接违反了“不含K₅”的要求。

延伸研究补充 #

如果你把条件再收紧，要求图里连K₄都不能有（也就是同时不含K₄和K₅），那这个问题就对应你提到的Denis Hanson等人的论文 "The size of a minimum five-chromatic K4-free graph" 了。这篇研究里证明了这类图的最小顶点数是19，是通过构造性的方法得到的优化结果。

内容的提问来源于stack exchange，提问作者karp