Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.

share|improve this question
    
Can you do the case $r=2$? and derive some insight from it? then maybe think about $r=3$? –  Gerry Myerson Jul 6 '12 at 0:19

2 Answers 2

up vote 3 down vote accepted

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

share|improve this answer

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

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.