[Solved] Explain Following Proof Work Huge Bug Problem Half Clique G Clique Size Least N 2 Proof Sh Q37187063

Explain why the following proof does not work. (It has a hugebug.)

Problem: Half-Clique. Does G have a clique of size at leastn/2?

Proof: To show Half-Clique is in NP, the certificate is a listof n/2 vertices. We can check the edges in polynomial time toensure that the vertices in the list form a clique of the rightsize in G.

Reduction: We reduce from Full-Clique below.

Full-Clique: Does G on n vertices contain a clique of sizen?

Take an arbitrary instance of Full-Clique, on G with n vertices.Add n vertices of degree 0 to G, to form G` on 2n vertices. Feed G`to Half-Clique. If G has a clique of size n, then G` will also havea clique of size n, which will be a Half-Clique on G` .

Now consider the other direction: G` has a half clique, since ithas 2n vertices, it mush have an n-clique. Since n of its verticesare not connected to any other vertices, those cannot be part ofthe clique, and the n clique must be on those copied from G. Then,those will also form a clique on G, thus G has a Full Clique.

Expert Answer

---

Answer to Explain why the following proof does not work. (It has a huge bug.) Problem: Half-Clique. Does G have a clique of size a… . . .