Connect these in a triangle. At least two vertices per triangle must be in the cover to take care of edges in the triangle, for a total of at least 2 C vertices. Finally, we will connect each literal in the flat structure to the corresponding vertices in the triangles which share the same literal. Select the N vertices cooresponding to the TRUE literals to be in the cover. Since it is a satisfying truth assignment, at least one of the three cross edges associated with each clause must already be covered - pick the other two vertices to complete the cover.
Every vertex cover gives a satisfying truth assignment .
Every vertex cover must contain n first stage vertices and 2 C second stage vertices. Let the first stage vertices define the truth assignment. To give the cover, at least one cross-edge must be covered, so the truth assignment satisfies. Let the N selected vertices from the first stage coorespond to TRUE literals. If there is a satisfying truth assignment, that means at least one of the three cross edges from each triangle is incident on a TRUE vertex.