TAOCP 7.2.2.2 Exercise 16

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

Verified: no
Solve time: 2m20s

Solution

No. The McGregor graph of order $n$ has no clique of size $4$.

Let the vertices be written as $(j,k)$, where $0\le j\le n$ and $0\le k<n$. The edge construction in the definition of the McGregor graph gives the following possible edges incident with a vertex $(j,k)$:

$$ (j,k)(j+1,k+1)\quad (j<n,\ k<n-1), $$

$$ (j,k)(n,n-1)\quad (j=0), $$

$$ (j,k)(j+1,k)\quad (j<n,\ j\ne k), $$

$$ (j,k)(j,k+1)\quad (k<n-1,\ j\ne k+1), $$

together with the exceptional edges involving the vertices with second coordinate $0$ or $n-1$ described in the definition of the graph.

Suppose that four vertices form a clique. Choose one vertex of the clique and call it $v$. The other three vertices must all belong to the neighborhood of $v$, and they must themselves be pairwise adjacent. Thus the neighborhood of every vertex in a McGregor graph would have to contain a triangle.

We examine the possible triangles in a neighborhood. The ordinary edges among vertices $(j,k)$ change the second coordinate by either $0$ or $1$, except for the exceptional edges to vertices of the form $(r,0)$ and $(r,n-1)$. Hence, among three neighbors of a fixed vertex, at most one can be obtained by each of the two diagonal directions

$$ (j,k)\longrightarrow (j+1,k+1),\qquad (j,k)\longrightarrow (j+1,k). $$

If two neighbors arise from these two different directions, their first coordinates differ by $0$ or $1$ and their second coordinates differ by $1$. The edge rules allow an edge between such a pair only when one of the equality restrictions in the construction fails, namely the restrictions

$$ j\ne k,\qquad j\ne k+1 . $$

The remaining exceptional edges cannot supply the missing adjacencies simultaneously. Each exceptional edge fixes either the second coordinate $0$ or the second coordinate $n-1$, and the two possible exceptional families meet only in the single vertices already accounted for by the ordinary cases.

Therefore the induced graph on the neighbors of any vertex contains no triangle. A clique of size $4$ would give a triangle inside the neighborhood of each of its vertices, which contradicts the preceding argument.

Hence no set of four vertices in a McGregor graph can be pairwise adjacent. Therefore McGregor graphs do not have cliques of size $4$.

This completes the proof.

$$ \boxed{\text{No, McGregor graphs have no cliques of size }4.} $$

∎