# 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.

• You are asking two questions: why does greedy not work, and whether there is any algorithm better than brute force. The usual rule is one question per post. – Yuval Filmus Sep 22 '16 at 21:16
• @YuvalFilmus sorry I'm not quite aware about the rules here, but judging from my experience on other stack exchange sites, I think that they are almost related. I don't know. But anyways... – RE60K Sep 22 '16 at 21:17
• Yuval is correct. I've edited out the second question, but you're welcome to ask it separately. No, they're two different questions, with different answers. If you still want to know the answer to the second question, you can ask it separately, after doing some research and self-study on it (there are many standard resources on the topic; you should read them before asking here, as there's little point in us duplicating standard material), and make sure to show us what research/self-study you've done in the question. And welcome to CS.SE! – D.W. Sep 23 '16 at 3:15

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$.