An (n-2)-dimensional Quadratic Surface Determining All Cliques and a Least Square Formulation for the Maximum Clique Problem

Arranging an n-vertex graph as the standard simplex in R , we identify graph cliques with simplex faces formed by clique vertices. An unstrict quadratic inequality holds for all points of the simplex; it turns to equality if and only if the point is on a face corresponding to a clique. This way this equality determines a quadratic surface in R characterizing all graph cliques. Since the standard simplex is a polyhedron located within the hyperplane e x = 1, we may decrease the dimensionality by 1 considering the intersection of this surface with the hyperplane. Therefore, we obtain a quadratic surface of dimensionality (n 2) determining all graph cliques. We call it the clique wrapper