TAOCP 7.2.2.2 Exercise 15

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: yes
Solve time: 1m03s

---

Solution

Let $K_n$ denote the complete graph on the vertex set ${1,2,\ldots,n}$. Its edges are the $2$-element subsets ${i,j}$ with $1 \le i < j \le n$.

The McGregor graph of order $n$ is defined as the line graph of $K_n$. Its vertices correspond to the edges of $K_n$, and adjacency corresponds to incidence in $K_n$.

Thus a vertex of the McGregor graph is a $2$-element subset

${i,j}, \quad 1 \le i < j \le n,$

and two distinct vertices ${i,j}$ and ${k,\ell}$ are connected by an edge if and only if the corresponding edges of $K_n$ share an endpoint, that is,

${i,j} \cap {k,\ell} \ne \emptyset.$

This condition is equivalent to

$i=k ;\lor; i=\ell ;\lor; j=k ;\lor; j=\ell,$

with ${i,j} \ne {k,\ell}$.

The number of vertices is the number of edges of $K_n$, hence

$|V_n| = \binom{n}{2} = \frac{n(n-1)}{2}.$

Fix a vertex ${i,j}$. It is adjacent to every vertex that contains $i$ or contains $j$, except itself. The vertices containing $i$ are

${i,k}, \quad k \in {1,\ldots,n} \setminus {i},$

and among these, ${i,j}$ is excluded, leaving $n-2$ choices. The same count holds for vertices containing $j$, again giving $n-2$ choices. No vertex can contain both $i$ and $j$ except ${i,j}$ itself, so these two families are disjoint.

Hence each vertex has degree

$\deg({i,j}) = (n-2) + (n-2) = 2(n-2).$

Summing degrees over all vertices and dividing by $2$ gives the number of edges:

$|E_n| = \frac{1}{2} \cdot |V_n| \cdot 2(n-2).$

Substituting $|V_n| = \binom{n}{2}$ yields

$|E_n| = \binom{n}{2}(n-2) = \frac{n(n-1)}{2}(n-2) = \frac{n(n-1)(n-2)}{2}.$

Thus the McGregor graph of order $n$ has vertex set

$V_n = \bigl{{i,j} : 1 \le i < j \le n\bigr},$

edge set defined by intersection of pairs, and cardinalities

$|V_n| = \frac{n(n-1)}{2}, \qquad |E_n| = \frac{n(n-1)(n-2)}{2}.$

This completes the solution. ∎