Let *FGCOLOR* = {⟨G⟩| *G* is a funny graph that is colorable so that every square vertex either has an out-edge to a green vertex or an in-edge from a red vertex}.

To show that *FGCOLOR* is NP-complete, first observe that *FGCOLOR* is in NP, since, given a graph *G* and a subset *S* of *G*'s nodes (the nodes marked as "square"), it would take linear time in the size of *S* to examine each node of *S* and verify that it meets the conditions of *FGCOLOR*.

Since *FGCOLOR* is in NP, we can show that *FGCOLOR* is NP-complete by giving a polynomial time reduction from *3SAT*. In this reduction, we make use of the correspondence between circular nodes in a graph which must be colored either green or red, and variables in a formula which must be assigned either true or false.

The reduction maps a 3cnf Boolean formula φ to a graph *G*. Construct *G* as follows:

- For each variable in φ, add a circular vertex to
*G* and label it with that variable's name.
- For each clause in φ, add a square vertex to
*G*. Then, for each square vertex, add edges as follows:
- If the corresponding clause in φ contains a literal that matches the label on a circular vertex, add an out-edge from the square vertex to the circular vertex.
- If the corresponding clause in φ contains a literal that contradicts the label on a circular vertex, add an in-edge to the square vertex from the circular vertex.

The following figure illustrates this construction when &phi = (*x*_{1} ∨ *x*_{1} ∨ *x*_{2}) ∧ (¬*x*_{1} ∨ ¬*x*_{2} ∨ ¬*x*_{2}) ∧ (¬*x*_{1} ∨ *x*_{2} ∨ *x*_{2}). (The red and green coloring of the circular vertices isn't part of the construction, but it illustrates a later point.)

Next, we show that φ is satisfiable if and only if ⟨*G*⟩ is in *FGCOLOR*. For the forward direction, suppose φ has a satisfying assignment. Color the circular vertices in *G* as follows: green if the corresponding variable in φ has been assigned true, and red if the corresponding variable has been assigned false. Since each clause in φ must evaluate to true, at least one literal in every clause must evaluate to true. That is, each clause must have at least one literal that either matches a variable that has been assigned true, or that contradicts a variable that has been assigned false. Therefore the square vertices representing each clause must have at least one of either an out-edge to a green vertex, or an in-edge to a red vertex. Therefore ⟨*G*⟩ is in *FGCOLOR*.

For the opposite direction, suppose ⟨*G*⟩ is in *FGCOLOR*. Then each circular vertex must be either red or green. Assign the variables in φ as follows: true if the corresponding circular vertex is green, and false if the corresponding circular vertex is red. Since each square vertex in *G* must have at least one of either an out-edge to a green vertex or an in-edge to a red vertex, each clause in φ must have at least one true literal. Therefore φ has a satisfying assignment.

We have shown that *FGCOLOR* is reducible from *3SAT* in polynomial time. Since *3SAT* is NP-complete and *FGCOLOR*is in NP, *FGCOLOR* is NP-complete.

The key idea of the reduction is that circular vertices have to be either green or red -- not both, and not neither -- and that Boolean variables have to be either true or false -- not both, and not neither. Once I finally noticed that, I could exploit the correspondence, letting green be true and red be false.