for the first two cases it is fairly easy to see that the original clause is satisfiable if and only if the resulting clauses are satisfiable for the case were we replaced clause with more than three literalsconsider the following if is satisfiablethen is satisfiableassume xm is assigned true then assign zt as false then all clauses in case ( are satisfied if xj are all falsethen zj- are all true but then (xj- xj- zj- is false next we define the problem vertex cover for use in further examples vertex coverinputa graph and an integer outputyes if there is subset of the vertices in of size or less such that every edge of has at least one of its endpoints in sand no otherwise example in this examplewe make use of simple conversion between two graph problems theorem vertex cover is -complete proofprove that vertex cover is in psimply guess subset of the graph and determine in polynomial time whether that subset is in fact vertex cover of size or less prove that vertex cover is -hardwe will assume that kclique is already known to be -complete (we will see this proof in the next example for nowjust accept that it is true given that -clique is -completewe need to find polynomialtime transformation from the input to -clique to the input to vertex coverand another polynomial-time transformation from the output for vertex cover to the output for -clique this turns out to be simple mattergiven the following observation consider graph and vertex cover on denote by the set of vertices in but not in there can be no edge connecting any two vertices in becauseif there werethen would not be vertex cover denote by the inverse graph for gthat isthe graph formed from the edges not in if is of size kthen forms clique of size in graph thuswe can reduce -clique to vertex cover simply by converting graph to and