Arranging an n-vertex graph as the standard simplex in R^n, 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^n 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. The higher the dimensionality of a standard simplex face, the less the distance from it to the geometric center of the simplex. Therefore, the maximum clique problem is equivalent to finding a point of the clique wrapper closest to the geometric center of the simplex and lying not outside the simplex. When the latter is relaxed, all stationary points of such a least square program can be found via roots of one univariate rational equation. If the adjacency matrix of the graph does not have multiple eigenvalues, the number of the stationary points is not above 2(n-1). If a clique is such that any vertex outside it has the same number of adjacent vertices in the clique, the geometric center of the clique face is such a stationary point.
Citation
Stas Busygin's NP-Completeness Page (http://www.busygin.dp.ua/npc.html), 2002.