Reduction of Boolean 3-Sat to Vertex Cover. Suppose that E is a boolean expression in conjunction normal form, where there are n clauses. Each clause consists of three terms, and each term is either a variable or the negation of a variable. Let m be the number of distinct variables. Note that m = O(n). Let x_1 , .... x_m be those variables. Thus each term is the form x_i or ~x_i for some i. Without loss of generality, the three variables of each clause are distinct. We now design a graph G with 4m(m+1) vertices and 5m^2 + 6m + n edges, such that G has a (3m^2/2 + 5m/2)-vertex covering if and only if E is satisfiable. There are two classes of vertex, which we "singletons" and "doubletons." Each vertex is labeled by a boolean expression. A singleton is labeled either x_i or ~x_i for some i. Thus, there are 2m singleton vertices. A doubleton is labeled either x_i + x_j, x_i + ~x_j, ~x_i + x_j, or ~x_i + ~x_j, for some i < j. We then create edges between pairs of vertices, labeling each vertex with a boolean expression which is the disjunction of the boolean expressions of its end vertices. There are four classes of edges, as follows: Class I. For each i, an edge between x_i and ~x_i. This edge is labeled with the boolean expression x_i + ~x_i. There are m edges in this class. Class II. For each i < j, we create 8 edges as follows: a) An edge between x_i and ~x_i + x_j, labeled x_i + x_i + x_j. b) An edge between x_i and ~x_i + ~x_j. c) An edge between ~x_i and x_i + x_j. d) An edge between ~x_i and x_i + ~x_j. e) An edge between x_j and x_i + ~x_j. f) An edge between x_j and ~x_i + ~x_j. g) An edge between ~x_j and x_i + x_j. h) An edge between ~x_j and ~x_i + x_j. There are 4m(m+1) edges in this class. Class III. For each i < j, we create 6 edges as follows: a) An edge between x_i + x_j and x_i + ~x_j. b) An edge between x_i + x_j and ~x_i + x_j. c) An edge between x_i + x_j and ~x_i + ~x_j. d) An edge between x_i + ~x_j and ~x_i + x_j. e) An edge between x_i + ~x_j and ~x_i + ~x_j. f) An edge between ~x_i + x_j and ~x_i + ~x_j. There are 3m(m+1) edges in this class. Class IV. For any clause of the form t_1+t_2+t_3, we create one edge between t_1+t_2 and t_3. There are n edges in this class. Given any assignment of values to the variables, exactly half, i.e., m, of the boolean expressions labeling the singleton vertices will be true, and exactly three fourths, i.e., 3m(m+1)/2, of the boolean expressions labeling the doubleton vertices will be true. The boolean expressions that label the edges of Classes I, II, and III are tautologies. Given a satisfying assignment, then the boolean expression labeling each edge of class IV will be true. Thus, if there is a satisfying assignment, there is a vertex cover of cardinality k =