证明或反驳：同顶点集的边不交图G、H满足χ(G∪H)≤χ(G)+χ(H)

嘿，你说得没错，这个命题确实是成立的！咱们可以用两种直观的方法来证明它：

这种方法通过逐步缩小图的规模来推导结论，逻辑非常清晰：

• 基础情况：当顶点集V的大小为1时，G、H和它们的并集都是无边图，色数全为1，显然满足 (1 \leq 1+1=2)，命题成立。
• 归纳假设：假设对于所有顶点数小于n的边不交图对，命题都成立——也就是任意两个顶点数为n-1的边不交图G'、H'，都有 (\chi(G'\cup H') \leq \chi(G')+\chi(H'))。
• 归纳步骤：考虑顶点数为n的图G和H，随便挑一个顶点v∈V。令G'=G-v（去掉v后的G），H'=H-v（去掉v后的H），那么 (G'\cup H'=(G\cup H)-v)。根据归纳假设，(\chi(G'\cup H') \leq \chi(G')+\chi(H'))，而去掉顶点不会增加图的色数，所以 (\chi(G')\leq\chi(G))、(\chi(H')\leq\chi(H))，因此 (\chi(G'\cup H') \leq \chi(G)+\chi(H))。
  现在给 (G'\cup H') 做一个 ((\chi(G)+\chi(H)))-正常着色。接下来处理顶点v：
  • 在G中，v的邻居们最多用了 (\chi(G)-1) 种不同颜色（毕竟G的色数是(\chi(G))，v本身可以用剩下的那1种颜色）；
  • 在H中，v的邻居们最多用了 (\chi(H)-1) 种不同颜色。
    这两部分邻居的颜色集合的并集大小最多是 ((\chi(G)-1)+(\chi(H)-1)=\chi(G)+\chi(H)-2)，也就是说，在(\chi(G)+\chi(H))种颜色里，至少还有2种颜色没被v的邻居用。随便选一种给v，就能保证v和它在G∪H里的所有邻居颜色都不同，这样就得到了G∪H的一个((\chi(G)+\chi(H)))-正常着色，所以 (\chi(G\cup H)\leq\chi(G)+\chi(H))。

我们可以利用G和H各自的正常着色，直接组合出G∪H的合法着色：
设(c_G)是G的一个(\chi(G))-正常着色（颜色集合是({1,2,...,\chi(G)})），(c_H)是H的一个(\chi(H))-正常着色（颜色集合是({1,2,...,\chi(H)})）。给每个顶点v分配一个有序对颜色((c_G(v), c_H(v)))。

现在验证这个着色的合法性：

• 如果u和v在G中相邻，那么(c_G(u)\neq c_G(v))，对应的有序对肯定不同；
• 如果u和v在H中相邻，那么(c_H(u)\neq c_H(v))，对应的有序对也肯定不同。

这个着色总共用了(\chi(G)*\chi(H))种颜色，而我们可以发现：

• 当其中一个图的色数为1时（比如(\chi(G)=1)，说明G是无边图），G∪H其实就是H，此时(\chi(G\cup H)=\chi(H)=1+\chi(H)=\chi(G)+\chi(H))，等号成立；
• 当(\chi(G)\geq2)且(\chi(H)\geq2)时，(\chi(G)\chi(H)\geq\chi(G)+\chi(H))（展开((\chi(G)-1)(\chi(H)-1)\geq1)就能得到这个结论），既然能用(\chi(G)\chi(H))种颜色着色，那肯定也能用更少的(\chi(G)+\chi(H))种颜色着色（毕竟色数是最小着色数，更大的颜色数肯定也能满足）。

所以不管哪种情况，(\chi(G\cup H)\leq\chi(G)+\chi(H))都成立。

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