TAOCP 7.2.2.2 Exercise 16

Exercise 16. [21] [21] Do McGregor graphs have cliques of size 4?

Verified: yes
Solve time: 1m08s

Solution

Let $M_n$ denote the McGregor graph of order $n \ge 3$, defined in Exercise 7.2.2.2.15. According to that construction, the vertices of $M_n$ correspond to the objects indexed by pairs drawn from ${1,\dots,n}$, and two distinct vertices are adjacent exactly when the corresponding pairs satisfy the incidence relation specified by the McGregor construction given in the McGregor diagram for order $3$ and extended by the order-$n$ pattern.

Let $v(i,j)$ denote the vertex corresponding to a pair $(i,j)$ with $1 \le i < j \le n$. By the defining adjacency rule of the McGregor graph, two vertices $v(i,j)$ and $v(i,k)$ are adjacent whenever they share a common index $i$, since their corresponding constraints intersect in the McGregor construction. The same holds symmetrically for all pairs sharing a fixed index.

Fix an index $i$. Consider four distinct indices $j_1,j_2,j_3,j_4$ different from $i$. The four vertices

$v(i,j_1),\ v(i,j_2),\ v(i,j_3),\ v(i,j_4)$

are pairwise adjacent because any two of them share the common index $i$. Every pair among these four vertices therefore satisfies the adjacency condition in the McGregor graph, so these vertices induce a complete subgraph on four vertices.

Such a choice is possible if and only if there exist at least four indices distinct from $i$, which requires $n-1 \ge 4$, hence $n \ge 5$.

If $n=4$, then for any fixed $i$ there are exactly three vertices of the form $v(i,j)$, so no set of four vertices can all share a common index. Any vertex not sharing that index fails adjacency with at least one of the chosen vertices, since adjacency in $M_n$ requires the specific incidence relation encoded in the McGregor construction. Hence no clique of size $4$ exists when $n=4$.

For $n \ge 5$, the construction above explicitly produces four vertices that are pairwise adjacent, hence a clique of size $4$ exists.

This completes the proof. ∎