2
$\begingroup$

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?

$\endgroup$

1 Answer 1

4
$\begingroup$

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:

enter image description here

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<n$, there is no regular $n$-vertex graph with clique number $k$, anyway.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .