chap limits to computation asking if has vertex cover of size or smaller if yesthen there is clique in of size kif no then there is not example so farour -completeness proofs have involved transformations between inputs of the same "type,such as from boolean expression to boolean expression or from graph to graph sometimes an -completeness proof involves transformation between types of inputsas shown next theorem -clique is -complete proofk-clique is in pbecause we can just guess collection of vertices and test in polynomial time if it is clique now we show that kclique is -hard by using reduction from sat an instance of sat is boolean expression cm whose clauses we will describe by the notation ci [ [ [iki where ki is the number of literals in clause ci we will transform this to an instance of -clique as follows we build graph { [ij]| < < < <ki }that isthere is vertex in corresponding to every literal in boolean expression we will draw an edge between each pair of vertices [ and [ unless ( they are two literals within the same clause ( or ( they are opposite values for the same variable ( one is negated and the other is notset figure shows an example of this transformation is satisfiable if and only if has clique of size or greater being satisfiable implies that there is truth assignment such that at least one literal [iji is true for each if sothen these literals must correspond to vertices in clique of size converselyif has clique of size or greaterthen the clique must have size exactly (because no two vertices corresponding to literals in the same clause can be in the cliqueand there is one vertex [iji in the clique for each there is truth assignment making each [iji true that truth assignment satisfies we conclude that -clique is -hardtherefore -complete