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.