part-ii/2015-66/

[tripos-comments[bot]]

Part II 2015 Graph Theory: Paper 1, Section II, I

https://questions.tripos.org/part-ii/2015-66/

[walrus1729]

Solution

Parts (a) and (b) are bookwork.

For part (c), we first show that

$$n = 1 + \frac{k(k+2)}{3}$$

To see this, consider an arbitrary vertex $x$, which has $k$ neighbours. The number of edges from these neighbours to other vertices in the graph (not including $x$, and there are no edges between neighbours of $x$ because $a=0$) is $k(k-1)$, since this is a $k$-regular graph. However, we need to divide this number by $3$ from the condition that $b=3$, since each vertex in $N(N(x))$ needs $3$ neighbours in common with $x$. Thus the total number of vertices is $|x| + |N(x)| + |N(N(x))|$, which is given by

$$1 + k + \frac{k(k-1)}{3} = 1 + \frac{k(k+2)}{3}$$

Substituting this expression and the values of $a$ and $b$ into the result from part (b) gives us that $\sqrt{4k-3}$ must be an integer dividing $k^2$ (note that we cannot have $k=0$). Let $\sqrt{4k-3} = t > 0$; then $k = \frac{t^2 + 3}{4}$.

Then $t$ divides $16k^2 = t^4 + 6t^2 + 9$, so $t$ divides $9$, so $t \in {1,3,9}$ and solving for $k$ gives us that $k \in {1,3,21}$. These correspond to $n = 2, 6, 162$. However, the first of these is impossible, since a $1$-regular graph on $2$ vertices is necessarily complete (and we are told that $G$ is incomplete), so $n \in {6,162}$ as required.