0
$\begingroup$

What $r$ colorable simple graph on $n$ vertices has the most edges? Is there a unique such graph? I am told this has something to do with Turan's theorem...

(This is the progress I have made- deleting a vertex $u$ and replacing it with a copy of a vertex $v$ preserves the number of vertices and $r$ colorability. When does, however, increase the number of edges? I also think that the same graph should work for the graph with the most edges and no $K_{r+1}$ subgraph.

A full fledged solution would be fantastic.

  • 0
    Can you do the case $r=2$? and derive some insight from it? then maybe think about $r=3$?2012-07-06

2 Answers 2

3

Hint: The maximal $K_{r+1}$-free graph happens to be $r$-colorable.

More on the hint: Turán's theorem bounds the number of edges that a $K_{r+1}$-free graph can have. The tight example is $r$-colorable. Since $K_{r+1}$ isn't $r$-colorable, Turán's theorem answers your question.

Another way to solve this uses David's method. Let $n_1,\ldots,n_r$ be the sizes of the color classes. We can assume that all edges connecting different color classes are there. The only edges not there are the within-class edges, which number $ \binom{n_1}{2} + \cdots + \binom{n_r}{2} = \frac{n_1^2 + \cdots + n_r^2}{2} - \frac{n}{2}. $ Since $n$ is constant, we might as well minimize $n_1^2 + \cdots + n_r^2$. Consider any two $n_1,n_2$ satisfying $n_2 - n_1 \geq 2$. If we increase $n_1$ by one and decrease $n_2$ by one then the new sum of squares is $ (n_1+1)^2 + (n_2-1)^2 = n_1^2 + n_2^2 + 2(n_1 - n_2 + 1) < n_1^2 + n_2^2. $ This shows that the optimum is achieved for a setting in which $|n_i - n_j| \leq 1$ for all $i,j$. Thus for some $m$ and $k$, wlog $n_1 = \cdots = n_k = m+1, \, n_{k+1} = \cdots = n_r = m.$ Since the total number of vertices is $n$, we must have $ n = k(m+1) + (r-k)m = rm + k. $ We can assume that $0 \leq k < r$ (i.e. $n_r = m$), hence $k = n \mod{r}$ and $m = \lfloor n/r \rfloor$.

2

Assume for simplicity $r \mid n$.

Consider the graph $G$ in which the vertices are partitioned into $r$ equal classes. (Each containing $n/r$ vertices) Every vertex is connected all the vertices in the other classes. This is clearly $r$-colorable, and has $n (r-1)/2$ edges.

On the other hand, if a graph $G$ is $r$-colorable, with classes of size $n_1, \dots, n_r$, then each class $i$ may have up to $n_i (n-n_i)$ edges emanating it. By double-counting, the total-number of edges is at most $\sum_i n_i (n - n_i)/2$. By concavity this is maximized at $n_i = n/r$.

So this graph $G$ achieves the maximum number of edges $n (r-1)/2$.