# Hueristic Algorithm to find the maximum clique

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.

Consider a graph which is the disjoint union of $K_i$ and $K_1$, the isolated vertex.
Then your heuristic outputs solution 1 for any $i \in \mathbb{N}$.