Reduction from 3-Coloring to Fair-3-Coloring
I am exercising for a final. The problem asks to show that the 3-Coloring problem polytime reduces to Fair-3-Coloring (3-Coloring <p Fair-3-Coloring), where:
Fair-3-Coloring:
Input: Graph
Output: "Yes" if each color is used exactly the same number of times. "No" otherwise.
So, in essence, I need to somehow modify the input of 3-Coloring (which is a graph) to match the input for Fair-3-Coloring, which is also a graph.
I am thinking that we must ensure that the total number of nodes is a multiple of 3. But then I am not sure how those nodes need to be connected.
They don't have to be connected. Just throw in some loose nodes. Those nodes are just there to fix the number of colours, they shouldn't be affecting colourability.
You have to add more than just 1 or 2 (which would be enough to get a multiple of 3) in general. For example consider this graph:
Two colours are each used 4 times, and the remaining colour is used once. So you'd have to add at least 3 nodes, even though the graph always had a number of nodes that is a multiple of 3. I'm not sure what the minimum number of nodes is that you have to add, but if you add 2n nodes it will definitely work. It's automatically a multiple of 3, and it will even work in the worst-imaginable case where the nodes in the graph all had the same colour, which only has to happen when there was only 1 node to begin with.