我正在为期末考试锻炼该问题要求证明3-着色问题的多时性减少为fair-3-着色（3-着色<pfair-3-着色），其中：
三色系：
输入：图形
输出：如果每种颜色使用的次数完全相同，则为“是”不“否则。
所以，本质上，我需要修改3-着色（这是一个图）的输入，以匹配fair-3-着色（这也是一个图）的输入。
我认为我们必须确保节点总数是3的倍数。但我不确定这些节点需要如何连接。
最佳答案
他们不必有联系。把一些松散的节点扔进去。这些节点只是用来确定颜色的数量，它们不应该影响可着色性。
一般来说，你需要添加的不仅仅是1或2（这足以得到3的倍数）例如，考虑这个图：
两种颜色各使用4次，其余颜色使用一次因此，您必须至少添加3个节点，即使图中的节点数总是3的倍数。我不知道你需要添加的最小节点数是多少，但是如果你添加2n个节点，它肯定会起作用。它自动地是3的倍数，甚至在最坏的情况下也能工作，图中的节点都有相同的颜色，只有在只有1个节点开始的时候才会发生。
关于algorithm - 从三色还原为三色，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/27474787/