# Possible clique numbers of a regular graph

I have been stuck on a question

Let $$G$$ be a regular graph on $$n$$ vertices. Show that the possible clique numbers (the clique number being the maximal order of a complete subgraph in $$G$$) are $$1,2,...,\lfloor \frac{n}{2}\rfloor, n$$.

Note that this question was asked on comp sci stack exchange, however, the one answer only shows that one can always construct a regular graph with a clique number $$\lfloor \frac{n}{2}\rfloor, n$$ and nothing intermediate. It does not show that one can definitely find a regular graph with a maximum complete graph of size 3, 4 ... say (with 1 and 2 it is trivial. For 1, you need the empty graph, and for 2, have a complete bipartite graph say if $$n$$ is even, or a cycle for any $$n$$).

I'm not sure if this is completely obvious. I thought it might be by construction, for instance if I was to make two $$\lfloor \frac{n-2}{2} \rfloor$$ complete graphs and the remaining vertices I would give them the same degrees. How do I know that when I ad these remaining vertices and their associated edges, I don't end up necessarily making a larger clique, so that there are 'gaps' in the possible clique numbers?

To construct an $$n$$-vertex regular graph with a clique of order $$k$$ (and no more), the easiest approach is to take a circulant graph in which we number the vertices $$0, 1, 2, \dots, n-1$$ and make vertices $$i, j$$ adjacent if $$i-j \bmod n$$ is one of $$\{-k+1,-k+2, \dots, -1, 1, 2, \dots, k-1\}$$. Here is an example with $$n=12$$ and $$k=4$$, and a clique of order $$4$$ highlighted:
We can check that, provided $$k \le \frac n2$$, no cliques of order more than $$k$$ are created. Take any clique, and without loss of generality, suppose that it contains vertex $$0$$. Then at most the $$2(k-1)$$ other vertices $$\{-k+1,-k+2, \dots, -1,1,2,\dots,k-1\}$$ can be in the clique. Moreover, these come in $$k-1$$ pairs $$\{-k+1,1\}, \{-k+2,2\}, \dots, \{-1,k-1\}$$, and at most one vertex from each pair can be in the clique (since the two vertices in a pair are not adjacent). This means there can be at most $$k-1$$ other vertices in the clique, so it has order at most $$k$$.
As soon as $$k \ge \frac{n+1}{2}$$, this argument stops working, because then pairs such as $$\{-1, k-1\}$$ are adjacent: although they are $$k$$ steps apart one way around the circle, they are $$k-1$$ steps apart or fewer the other way around. But as soon as $$k \ge \frac{n+1}{2}$$ but $$k, there is no regular $$n$$-vertex graph with clique number $$k$$, anyway.