Why doesn't greedy work for Clique?

In reference to this problem (equivalently, findind a maximal clique in an undirected graph), I believe greedy approach should work (i.e. removal of people who have maximal qualms with others.). Though I cannot prove that this would always work or won't but I intuitively felt that it should, but eventually some examples could be created that fail this greedy approach.

Can someone prove/disprove whether the greedy approach is correct? Not just a counterexample, but a general explanation would be quite useful.

Consider the graph consisting of a clique on $n/3$ vertices and a complete bipartite graph with $n/3$ vertices on either side. The degree of each vertex in the clique is $n/3-1$, whereas every vertex in the bipartite graph has degree $n/3$. Your algorithm would thus remove all the vertices in the clique. The remaining graph is bipartite, and so its maximal clique contains only two vertices.

So your algorithm finds a clique of size two instead of a clique of size $n/3$.

StackExchange Computer Science Q#63784, answer score: 4