Now we have to introduce some extra constraints so that this truth assignment has to be satisfied.
And to do that, we're going to introduce a set of nodes
for each clause that is sometimes referred to as a gadget.
These gadgets come up a lot in NP-completeness proofs.
In this case, it's going to be a little piece of a graph but it's going to be a little piece of a graph that has
particular mechanics to it that makes the graph act like a three-set problem.
All right, now we're going to extend this graph by adding a gadget for each clause.
A gadget is going to be a little chunk of a graph but it's going to have very particular property to it
that it's going to be three-colorable in the context to the rest of the graph
if and only if the corresponding clause is satisfiable in the context of the assignment.
So let's imagine that we've got, this is our clause (l₁, l₂, l₃).
All right, there's a couple different ways of making this gadget,
Here's one that makes sense to me.
Essentially, these are going to be little triangles, that kind of correspond to or expressions
and the or of l₁ and l₂ or'd with l₃ is going to give us the answer for the clause.
So, here's the sixth node.
They're going to be connected to some of the nodes that are already in the graph.
In particular, the three literals that are in that clause and the slack variable in the middle
slack node in the middle and false node off the side
and just to simply things, remind you that false node is colored black, the slack node is colored red,
and this literal nodes are either going to be blue or black each one.
And now, what I'd like to do is show you the different ways of coloring these
either allow the rest of this structure to be colored with three colors or not.
So let's start off with the case where all three of the literals are false.
That's an important case because if the assignment is such
that the literals are all false then this clause it's not satisfied.
This clause is not satisfied so the whole formula is not satisfied.
So this is going to be important to make sure that this graph is not going to be colorful.
So given that these two nodes are connected to slack, neither of them can be red.
So this one in particular can either be blue or black.
If this one is color blue, then that means neither of this can be colored blue
and neither of these can be colored black, so they have to be both colored red and that doesn't work.
So this can't be blue and it can't be red, so it has to be black.
This can either be blue or red, it doesn't matter which is which.
All right, so now we have this node.
Well this node is kind of obvious, it's connected to red and black, so it has to be blue.
Now this node is connected to blue and black, so it has to be red.
And this node is connected to red, blue, and black so we are in trouble.
So the graph was not colorable when these three literals are all black.
But if this literal is blue, well that means that one of the literals in clause is true,
so the whole clause should be true so this better be colorable.
Okay, by the same argument before, this is red and black so this one has to be blue as well.
So looks like we're okay.
We're able to assign colors to all these nodes so that none of the coloring constraints are violated.
So that's okay. So this one is blue and these guys are black.
Actually this one doesn't matter what it is, that thing is colorable.
So this could either be blue or black. What if this one was blue, that's going to be okay too.
We can just swap the two colors of these nodes.
All right, so what that means is if this one is blue, the thing is colorable. Definitely.
So one of them is true, that's if this one is true, that's enough.
So let's consider the case where this one is black and one of the other guys is blue.
All right, so this one is forced to be blue.
Since this one is black and this one is blue, this one is forced to be red,
which means this one's forced to be black which means this one's forced to be blue
and now we're in good shape because this one is black and this one is red
and now we have a valid coloring, actually no matter what l₂ is colored.
In the same argument where it's to be switched, which one of these two is blue?
We can just swap these two colors and everything is fine. So what did we just show?
So, this gadget for this clause is colorable as long as
the three literals it's connected to are not all black.
And that's great because that's exactly what the satisfiability condition is.
So we create one of these gadgets for each for each in the clauses
connect them to the rest of the graph and now we get this giant graph
and that whole graph is satisfied, if and only all the gadgets can be colored,
which is the same as saying if and only all the clauses can be satisfied
and since they're all connected with n, that's exactly what we wanted it to be.
So this graph that we built is colorable if and only the entire formula is satisfiable. That's kind of cool.
Right. So, even though a formula with boolean variables in it
and a graph with different colors in it, feel like very different problems
in a very deep fundamental mathematical way, they're really the same problem.