Let the algorithm be defined as follows:
Consider the following heuristic algorithm for finding the maximum size clique in a graph. (1). Delete from the graph a vertex that is not connected to every other vertex. (2). Repeat (1) until the remaining graph is a clique.
Now, how do I show that this algorithm does not give a solution which is within constant times of the optimal solution? I was reading about heuristic algorithms when I came across this problem. Any sort of input is appreciated.