But you accept that it can be colored with (at most) four colors, e.g. by coloring the central one color 1 and the other one billion color 2? Then you also can

But you accept that it can be colored with (at most) four colors, e.g. by coloring the central one color 1 and the other one billion color 2? Then you also can imagine the reduction. Each of these outer-inner node pairs is a reduction. Your big graph consists of overlaying one billion two-node graphs by merging on the color 1 node.