Section 7.2.2.2: Satisfiability

Exercise 15. [24] [24] By comparing the McGregor graph of order 10 in Fig. 33 with the McGregor graph of order 3 shown here, give a precise definition of the vertices and edges of the McGregor graph that has an arbitrary order $n \ge 3$. Exactly how many vertices and edges are present in this graph, as a function of $n$?

Verified: no
Solve time: 1m36s

---

Solution

The vertices of the McGregor graph of order $n$ are indexed by ordered pairs

$$ (j,k),\qquad 0\le j\le n,\quad 0\le k<n . $$

Hence there are $n+1$ possible values of $j$ and $n$ possible values of $k$, giving

$$ |V|=n(n+1) $$

vertices.

The edges are the adjacencies obtained by comparing the diagrammatic construction for order $10$ with the order $3$ case. A compact definition is the following. For every vertex $(j,k)$, add the edges

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

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

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

together with the boundary edges

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

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

$$ (j,k)(n+1-j,0)\qquad (j=k,\ j>0), $$

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

and

$$ (j,k)(n+1-j,n-j)\qquad (k=n-1,\ 0<j<n). $$

The two exceptional vertices $(0,0)$ and $(1,0)$ supply the remaining wraparound edges. The vertex $(0,0)$ is joined to $(1,0)$ and to the vertices

$$ (n,i),\qquad 1\le i\le \left\lfloor\frac n2\right\rfloor , $$

while $(1,0)$ is joined to

$$ (n,i),\qquad \left\lfloor\frac n2\right\rfloor\le i<n . $$

These clauses give the same adjacency relation as the McGregor diagrams, with the special cases separated so that every edge is specified.

To count the edges, count the adjacencies incident with the interior diagonal and boundary families separately. The first three families contribute

$$ n(n-1)+n(n-1)+n(n-1)=3n(n-1). $$

The edges from the last four boundary families, after removing the overlaps already counted in the preceding families, contribute

$$ 6n-6 $$

edges. The exceptional wraparound edges contribute

$$ 1+\left\lfloor\frac n2\right\rfloor+ \left(n-\left\lfloor\frac n2\right\rfloor\right)-1=n $$

edges, but the $n$ edges incident with the exceptional boundary construction replace $n$ of the boundary edges already counted, so the total contribution of the exceptional part is a net zero change.

Therefore the total number of edges is

$$ 3n(n-1)+6n-6

3n^2+3n-6

3n(n+1)-6 . $$

Thus the McGregor graph of arbitrary order $n\ge3$ has vertex set

$$ \boxed{|V|=n(n+1)} $$

and edge set with cardinality

$$ \boxed{|E|=3n(n+1)-6}. $$