Help reducing 3-SAT to 3-COLORING I am working on showing that 3-colorability is NP-complete. I read a few articles and walkthroughs on this but none are really clicking. I get to this part


  "Then for every variable xi that appears in the instance of Satisfiability, we connect a
       vertex xi to a vertex xi, and we connect both xi and xi to red. This is illustrated
       below for a case where there are (only) 3 variables."


I think what they mean is something like this:

x1----x1*     x2----x2*      x3----x3*
 \   /         \   /          \   /
  \ /           \ /            \ /
   R             R              R


But my question is, what exactly is this step doing? 

With a little bit more thought, is this step just showing that given xi to be one color, then xi* has to be another, but also cannot be R, as they are both connected to it?
I believe the goal of this construction is to try to assign true or false to each variable. The color assigned to x will determine whether it's true or false, and there's an edge from x to &not;x to ensure that each variable and its negation get different values. The edge from each variable to R ensures that there are only two possible colors that can be assigned to x, one of which means true and one of which meand false.

Hope this helps!