Exercise 17 (Cliques in Simple Graphs, III). This continues the examination of the clique problem in Example 15 and Exercise 16. We say that a set A of propositional wff's is

satisfied by G iff, for every & A, it is the case that is satisfied by G. The latter notion is defined in Example 15. Let k> 1 be fixed. Show that it is possible to define an infinite set I'(G) of propositional wff's over the set of variables X (as defined in Example 15) such that for every simple graph G, finite or infinite, it is the case that I'(G) is satisfied by G iff G does not contain a k-clique. Thus, the absence of k-cliques in a graph G, finite or infinite, can be expressed by a set I(G) of propositional wff's. Note the contrast with the conclusions in Example 15 and Exercise 16, where it is pointed out that the presence of k-cliques in an infinite graph G cannot be expressed in PL, whether by a single wff or by a set of wff's. Hint: If G does not contain a k-clique, then it does not contain a k'-clique for every k'> k. You need to show that every finite subset of I'(G) can be satisfied, and then invoke Compactness.