顶点着色：我们如何知道这是最佳着色？
Vertex Coloring : How do we know that this is an optimal coloring?
我正在解决这个与顶点着色相关的问题。在问题的解决方案部分，它说：
"The coloring is optimal because the graph contains the complete graph (clique) K4."
同样在另一个问题中，同样的解释是：
"The coloring is optimal because the vertices 1 to 5 form a complete subgraph K5."
为什么顶点着色（或边缘着色？）必须是最佳的，因为它包含一个完整的图形？我已经完成了所有的讲义和幻灯片，但是有没有这样的信息。
提前感谢您的帮助！
这些论点适用于一个非常具体的案例。他们表明第一个图的着色不能少于 4 种颜色，第二个图的着色不能少于 5 种颜色。所以第一个图的任何4色都是最优的，第二个图的任何5色都是最优的。
包含 K4 的图永远不能用少于 4 种颜色着色，因为子图禁止这样做。 K4 有四个节点都相互连接，所以每个节点都必须有不同的颜色，所以你只需要 4 种颜色用于该子图。如果那个子图已经需要 4 种颜色，那么整个图肯定需要 - 尽管它可能需要更多（在这种情况下你需要一种不同类型的最优性证明）。
查看图形着色约束的另一种方法（在这种情况下可能会有帮助）是将每个集团解释为全不同约束。
我正在解决这个与顶点着色相关的问题。在问题的解决方案部分，它说：
"The coloring is optimal because the graph contains the complete graph (clique) K4."
同样在另一个问题中，同样的解释是：
"The coloring is optimal because the vertices 1 to 5 form a complete subgraph K5."
为什么顶点着色（或边缘着色？）必须是最佳的，因为它包含一个完整的图形？我已经完成了所有的讲义和幻灯片，但是有没有这样的信息。
提前感谢您的帮助！
这些论点适用于一个非常具体的案例。他们表明第一个图的着色不能少于 4 种颜色，第二个图的着色不能少于 5 种颜色。所以第一个图的任何4色都是最优的，第二个图的任何5色都是最优的。
包含 K4 的图永远不能用少于 4 种颜色着色，因为子图禁止这样做。 K4 有四个节点都相互连接，所以每个节点都必须有不同的颜色，所以你只需要 4 种颜色用于该子图。如果那个子图已经需要 4 种颜色，那么整个图肯定需要 - 尽管它可能需要更多（在这种情况下你需要一种不同类型的最优性证明）。
查看图形着色约束的另一种方法（在这种情况下可能会有帮助）是将每个集团解释为全不同约束。