CS 163 / CS 265 Homework 8, due Friday, March 8


1. Must a graph whose maximum clique size is two be bipartite? Why or why not?


2. Give an example of a connected graph whose smallest maximal clique has size three and whose maximum clique has size five.


3. In the example we went through in class, every leaf of the recursion tree of the Tomita et al version of the Bron-Kerbosch algorithm (algorithm bk-ttt) produced as output a maximal clique. Find an example input for which one of the recursive calls made by this algorithm returns without outputting anything.


4. Let G be a graph with an even number n of vertices and with exactly 1.5n edges. What is the maximum value that the clustering coefficient of G might take? What is the minimum value that it might take? Describe two graphs (for a single value of n that you may choose, but the same value for both graphs) that have the given number of edges and achieve these maximum and minimum values.


5* (265 only). Describe a linear time algorithm for finding a single maximal clique in a given graph. What data structures does your algorithm need to maintain as it progresses (if any) in order to perform its operations efficiently?