TAOCP 7.2.1.3 Exercise 71

Let $G$ be a simple graph with $m=10^6$ edges, and let $K_t(G)$ denote the number of $t$-cliques in $G$.

taocpmathematicsalgorithmsvolume-4math-medium

Section 7.2.1.3: Generating All Combinations

Exercise 71. [M20] [M20] How many t-cliques can a million-edge graph have?

Verified: no
Solve time: 15m08s

Solution

Let $G$ be a simple graph with $m=10^6$ edges, and let $K_t(G)$ denote the number of $t$-cliques in $G$.

A $t$-clique is determined by a $t$-subset of vertices whose induced subgraph contains all $\binom{t}{2}$ edges. Each such clique uses $\binom{t}{2}$ edges, but edges can be shared among different cliques, so the problem is an extremal distribution problem over graphs with fixed edge count.

Let the vertex set be partitioned into disjoint sets $V_1, V_2, \dots, V_r$, where each $V_i$ induces a complete graph $K_{k_i}$ and there are no edges between different parts. Such a graph contains exactly

$\sum_{i=1}^r \binom{k_i}{t}$

$t$-cliques, since every $t$-clique must lie entirely within one complete component.

Any graph with a given number of edges can be transformed, without decreasing the number of $t$-cliques, into a disjoint union of cliques by repeatedly applying the standard edge-moving argument: if two vertices in different components have a missing edge internally, shifting edges to complete a denser component increases the number of completed $t$-vertex sets, and this operation preserves the total number of edges. Iterating this concentrates all edges into one complete graph, since the function $f(k)=\binom{k}{t}$ is convex in the sense that merging two clique sizes $a,b$ into $a+b$ increases the value whenever edges are sufficient to realize the merge.

Hence the maximum is achieved by a single clique $K_k$ with

$\binom{k}{2} \le 10^6,$

and all remaining vertices isolated.

We determine the largest such $k$ from

$\frac{k(k-1)}{2} \le 10^6,$

which is equivalent to

$k^2 - k - 2\cdot 10^6 \le 0.$

The positive root is

$k = \frac{1 + \sqrt{1 + 8\cdot 10^6}}{2} = \frac{1 + \sqrt{8,000,001}}{2}.$

Since

$2828^2 = 7,997,584,\qquad 2829^2 = 8,003,241,$

we have

$2828^2 < 8,000,001 < 2829^2,$

so

$\sqrt{8,000,001} \in (2828, 2829).$

Therefore

$\frac{1 + \sqrt{8,000,001}}{2} \in \left(1414.5, 1414.999\ldots\right),$

and the largest integer $k$ satisfying the edge constraint is

$k=2828.$

The clique $K_{2828}$ uses

$\binom{2828}{2} = \frac{2828\cdot 2827}{2} = 7,997,584 \le 10^6,$

so it is feasible, while $k=2829$ is not.

Thus the extremal graph is a complete graph on $2828$ vertices plus isolated vertices, and the number of $t$-cliques is

$\binom{2828}{t}.$

This value is maximal because any redistribution of edges among multiple components strictly reduces the largest achievable clique size and cannot compensate via smaller binomial contributions in $\binom{k}{t}$.

Therefore the maximum possible number of $t$-cliques is

$\boxed{\binom{2828}{t}}.$