Day: June 1, 2026

The Motzkin-Straus Theorem


To fully comprehend this topic, a basic understanding of multivariable calculus is required. A highly recommended reference is [1], specifically Theorem 2.4.15.

Let \displaystyle G be a simple, undirected graph with vertices labeled as \displaystyle 1, 2, \dots, n. Let \displaystyle S be the set of all non-negative real vectors whose components sum to \displaystyle 1:

\displaystyle S = \left\{ x = (x_1, x_2, \dots, x_n) \in \mathbb{R}^n \;\middle|\; x_i \ge 0 \text{ for all } i=1,\dots,n, \text{ and } \sum_{i=1}^{n} x_i = 1 \right\}.

For any vector \displaystyle x \in S, we define the objective function \displaystyle f(x) as the sum of the products of the weights associated with adjacent vertices in \displaystyle G:

\displaystyle f(x) = \sum_{(i,j) \in E} x_i x_j. \qquad (1)

Here, each edge \displaystyle (i,j) = (j,i) \in E is counted exactly once. The Motzkin-Straus theorem investigates the maximum value of this function over the set \displaystyle S, denoted as:

\displaystyle f(G) = \max_{x \in S} f(x) = \max_{x \in S} \sum_{(i,j) \in E} x_i x_j.

Remark on Existence: The function \displaystyle f(x) defined in (1) is a polynomial, which implies it is continuous everywhere on \displaystyle \mathbb{R}^n. Furthermore, the domain \displaystyle S is a closed and bounded set (a compact set) in \displaystyle \mathbb{R}^n. According to the Extreme Value Theorem, any continuous real-valued function attains both a global maximum and a global minimum on a closed and bounded domain. Therefore, the maximum value \displaystyle f(G) is strictly guaranteed to exist.

Theorem (Motzkin-Straus, 1965). Let \displaystyle k be the clique number (the order of the largest complete subgraph) of \displaystyle G. Then

\displaystyle f(G)=\frac{1}{2}\left(1-\frac{1}{k}\right). \qquad (2)

Proof. Suppose \displaystyle x = (x_1, x_2, \dots, x_n) is a point in \displaystyle S that maximizes the function

\displaystyle f(x) = \sum_{(i,j)\in G} x_i x_j.

Let \displaystyle V_x = \{i \mid x_i > 0\} be the set of vertices with positive weights. Suppose \displaystyle V_x does not induce a complete subgraph (clique). Then, there exist at least two vertices \displaystyle u, v \in V_x that are not adjacent in \displaystyle G.

Let \displaystyle S_u = \sum_{j \in N(u)} x_j and \displaystyle S_v = \sum_{j \in N(v)} x_j be the sum of the weights of the neighbors of \displaystyle u and \displaystyle v in \displaystyle G, respectively. Without loss of generality, assume that \displaystyle S_u \le S_v.

We construct a new weight distribution \displaystyle x' by shifting the entire weight of \displaystyle u to \displaystyle v:

  • \displaystyle x'_u = 0
  • \displaystyle x'_v = x_u + x_v
  • \displaystyle x'_i = x_i for all \displaystyle i \neq u, v.

It is clear that \displaystyle x' \in S because the total weight remains \displaystyle 1 and all weights remain non-negative. The change in the objective function is given by

\displaystyle f(x') - f(x) = x_u (S_v - S_u).

Since \displaystyle x_u > 0 and \displaystyle S_v \ge S_u, we have \displaystyle f(x') \ge f(x). However, because \displaystyle x is already a global maximizer, it must hold that \displaystyle f(x') = f(x).

The new point \displaystyle x' still achieves the maximum value, but the number of vertices with positive weights has decreased by 1 (since \displaystyle x'_u = 0). We repeat this weight-shifting process for any remaining pair of non-adjacent vertices with positive weights. This process must terminate after a finite number of steps. Upon termination, all vertices with positive weights must be mutually adjacent, meaning they form a complete subgraph \displaystyle C.

Let \displaystyle m be the number of vertices in \displaystyle C. Since \displaystyle k is the clique number of \displaystyle G, we must have \displaystyle m \le k. On the complete subgraph \displaystyle C, all vertices are pairwise adjacent, so

\displaystyle f(x) = \sum_{(i,j) \in C} x_i x_j = \frac{1}{2} \left( \left( \sum_{i \in C} x_i \right)^2 - \sum_{i \in C} x_i^2 \right).

Since the sum of the weights on \displaystyle C is \displaystyle \sum_{i \in C} x_i = 1, we obtain

\displaystyle f(x) = \frac{1}{2} \left( 1 - \sum_{i \in C} x_i^2 \right).

By the Cauchy-Schwarz inequality, we have

\displaystyle \sum_{i \in C} x_i^2 \ge \frac{1}{m} \left( \sum_{i \in C} x_i \right)^2 = \frac{1}{m}.

This implies \displaystyle f(x) \le \frac{1}{2} \left( 1 - \frac{1}{m} \right).

Since the function \displaystyle g(m) = \frac{1}{2}\left(1 - \frac{1}{m}\right) is strictly increasing with respect to \displaystyle m and \displaystyle m \le k, we get:

\displaystyle f(x) \le \frac{1}{2} \left( 1 - \frac{1}{k} \right). \qquad (3)

Now, choose a maximum complete subgraph of \displaystyle G with order \displaystyle k. Assume the vertices of this subgraph are \displaystyle 1, 2, \dots, k. By distributing the total weight equally among these \displaystyle k vertices and setting the weights of all other vertices to \displaystyle 0, i.e.,

\displaystyle x_1 = x_2 = \dots = x_k = \frac{1}{k} \quad \text{and} \quad x_{k+1} = \dots = x_{n} = 0,

we can compute the value of the objective function at this specific point as:

\displaystyle f(x) = \binom{k}{2} \cdot \frac{1}{k^2} = \frac{k(k-1)}{2} \cdot \frac{1}{k^2} = \frac{1}{2} \left( 1 - \frac{1}{k} \right). \qquad (4)

Combining (3) and (4), we conclude that the maximum value of the objective function on the set \displaystyle S is precisely \displaystyle f(G) = \frac{1}{2}\left(1 - \frac{1}{k}\right).

This completes the proof. ∎

Corollary (Turán’s Theorem). Let \displaystyle G be a graph with \displaystyle n vertices and edge set \displaystyle E. If \displaystyle G contains no complete subgraph of order \displaystyle k+1 (meaning the clique number of \displaystyle G does not exceed \displaystyle k), then the number of edges in \displaystyle G satisfies

\displaystyle |E| \le \frac{n^2}{2} \left( 1 - \frac{1}{k} \right).

Proof. Consider the uniform weight distribution \displaystyle x = \left(\frac{1}{n}, \frac{1}{n}, \dots, \frac{1}{n}\right). Clearly, \displaystyle x \in S since all coordinates are non-negative and their sum equals 1.

Evaluating the objective function \displaystyle f(x) at this point, each edge \displaystyle (i,j) \in G contributes exactly \displaystyle \frac{1}{n} \cdot \frac{1}{n} = \frac{1}{n^2}. Since the graph \displaystyle G has \displaystyle |E| edges, we have:

\displaystyle f(x) = \sum_{(i,j) \in G} x_i x_j = \sum_{(i,j) \in G} \frac{1}{n^2} = \frac{|E|}{n^2}.

On the other hand, by the Motzkin-Straus Theorem, the value of \displaystyle f(x) at any point in \displaystyle S cannot exceed the global maximum \displaystyle f(G). Let \displaystyle m be the clique number of \displaystyle G. By hypothesis, \displaystyle m \le k. Therefore:

\displaystyle f(x) \le f(G) = \frac{1}{2} \left( 1 - \frac{1}{m} \right) \le \frac{1}{2} \left( 1 - \frac{1}{k} \right).

Combining these two results, we obtain \displaystyle |E| \le \frac{n^2}{2} \left( 1 - \frac{1}{k} \right).

The inequality is thus proven. ∎

References
[1] Jerry Shurman, Calculus and Analysis in Euclidean Space (pages 23-56).