Proving Clique Number of a Regular Graph
Let $G$ be a $d$-regular graph on $n$ vertices containing an $a$-clique $A$, and let $B$ denote the other $b:=n-a$ vertices. Suppose that $a&gt;b$.

Let $e$ be the number of edges connecting $A$ to $B$. Every vertex in $A$ has $a-1$ edges going to the other vertices in $A$, and so $d-(a-1)$ edges going to vertices in $B$. Hence $e = a(d-(a-1))$. Similarly, every vertex in $B$ has at most $b-1$ edges going to the other vertices in $B$, and so at least $d-(b-1)$ edges going to vertices in $A$. Hence $e \geq b(d-(b-1))$. It follows that
$$ b(d-(b-1)) \leq a(d-(a-1)). $$
Subtracting the left-hand side from the right=hand side, we get
$$
0 \leq (ad-a^2+a)-(bd-b^2+b) = (ad-bd)-(a^2-b^2)+(a-b) = (a-b)(d-a-b+1).
$$
Since $a &gt; b$, it follows that $d \geq a+b-1 = n-1$. In other words, $G$ is the complete graph.

Summarizing, if a regular graph contains a clique on more than half the vertices then it is the complete graph. Therefore the clique number of a regular graph is either at most $\lfloor n/2 \rfloor$ or $n$.



Let us now show that the upper bound $\lfloor n/2 \rfloor$ is tight. That is, for every $n$ there exists a regular graph on $n$ vertices whose clique number is $\lfloor n/2 \rfloor$.

When $n$ is even, there exist regular graphs on $n$ vertices with clique number $n/2$, for example two disjoint copies of $K_{n/2}$.

When $n=4m+1$, there exist regular graphs on $n$ vertices with clique number $2m$: take two disjoint copies of $K_{2m}$, add a new vertex connected to $m$ vertices from each copy of $K_{2m}$, and add a matching between the remaining $m$ vertices of each copy of $K_{2m}$. When $m=1$, this gives the 5-cycle.

When $n=4m+3$, the following construction gives a regular graph on $n$ vertices with clique number $2m+1$. Take two disjoint copies of $K_{2m+1}$, say on vertices $x_1,\ldots,x_{2m+1}$ and $y_1,\ldots,y_{2m+1}$. Connect $x_i$ to $y_i$ for all $i$, and connect $x_i$ to $y_{i+1}$ for $i=1,\ldots,m$. Finally, add an additional vertex connected to $x_{m+1},\ldots,x_{2m+1}$ and to $y_1,y_{m+2},\ldots,y_{2m+1}$.