Chapter 27
Maximal Cliques, a Computer Science Example, and the Tennis Ball Problem
Our first example deals with graph theory and uses the result of Example 26.6. As we progress, we shall learn how the three topics for this chapter are related.
Example 27.1: If G = (V, E) is an undirected graph with vertex set V and edge set E, we say that the nonempty subset W of V induces a clique in G, if for all vertices a, b 
W, the edge ab(= ba) E. Hence the subgraph of G made up of the vertices in W together with all the possible edges determined by the vertices from W is a complete graph.
In Fig. 27.1 (a) we have an undirected graph G = (V, E), with 
and E = {vw, vy, vz, wx, wy, wz, xy, yz}. The undirected graph in part (b) of the figure is a clique for the undirected graph G. This is the clique induced by the vertex set 
. In Fig. 27.1 (c) we find another clique from G—this one induced by the vertex set 
. Note that Fig. 27.1 (d) provides the clique induced by . This clique is a subgraph (actually, ...
