0
$\begingroup$

I am very new to Graph Theory and I am trying to prove the following statement from a problem set for my class:

Prove that if G is a regular graph on n vertices $(n \ge 2)$, then $\omega(G) \in \{1, 2, 3,... \lfloor n / 2 \rfloor, n\}$

I am confused by the part where it places the clique number to be in this set: $\omega(G) \in \{1, 2, 3,... \lfloor n / 2 \rfloor, n\}$. Why can the clique number be only in the first half of this set (or it can be n) and why can't it be anything between $\lfloor n / 2 \rfloor$ and $ n$?

How can I go about proving this claim? Any tips would be appreciated.

$\endgroup$
  • 1
    $\begingroup$ You say that you are not sure why the statement holds. This is exactly the goal of this exercise, to understand why the statement holds! You can start by trying to construct a counterexample and see why it doesn't work. $\endgroup$ – Yuval Filmus Apr 17 '18 at 14:00
  • $\begingroup$ A good way to think of the exercise is as follows: if a regular graph contains a clique on more than $n/2$ vertices then it is the complete graph. $\endgroup$ – Yuval Filmus Apr 17 '18 at 14:00
0
$\begingroup$

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>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 > 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}$.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy