Suppose set $A$ with $2n$ elements. Construct simple graph $G$ with $\left(\begin{array}{c}2n\\ n\end{array}\right)$ vertices each one represents one of $n$_sized subsets of $A$ .Connect any two vertices of $G$ with an edge if and only if their corresponding subsets of $A$ , have one element in common or none(at most one element in common) .Prove that the chromatic number of $G$ is $6$ . In other word we can always color each vertex of $G$ such that no two adjacent vertex have the same color and also we can not do it with $5$ colors.


Its not difficult to show that we can do it with 6 colors , but how to prove that 5 colors are not enough and its not possible with 5 colors?

  • $\begingroup$ What have you tried? We are dealing with the complement of a Kneser graph, and the chromatic number of Kneser graphs is well known since Lovasz. $\endgroup$ – Jack D'Aurizio Jul 18 '16 at 19:19
  • 3
    $\begingroup$ Do you mean at least? It seems incorrect. Let $2n$ be large, like $60$. Surely we can find $10$ subsets of $\{1,\dots,60\}$ of size $30$ such that any two have an element in common. They can all for example contain the number $1$. $\endgroup$ – André Nicolas Jul 18 '16 at 19:21
  • $\begingroup$ No , we connect any two vertices if and only if their corresponding subsets have one element in common or none . And notice that we can not find 10 subsets in $n=30$ such that any two are connected since any two of them must have at last one element in common and should differ a lot ! $\endgroup$ – Ypical Jul 18 '16 at 19:39
  • $\begingroup$ sorry i mean at most $\endgroup$ – Ypical Jul 18 '16 at 19:50
  • $\begingroup$ @Ypical: I guess "at last" could be interpreted as meaning "at most", but the phrase is not in common use in mathematical English. My example was for the interpretation "at least". $\endgroup$ – André Nicolas Jul 18 '16 at 20:26

Choose three distinct numbers $a,b,c\in\{1,\dots,2n\}.$

Color a vertex $X$ with
color $1$ if $X\cap\{a,b,c\}\supseteq\{a,b\},$
color $2$ if $X\cap\{a,b,c\}=\{a,c\},$
color $3$ if $X\cap\{a,b,c\}=\{b,c\},$
color $4$ if $X\cap\{a,b,c\}=\{a\},$
color $5$ if $X\cap\{a,b,c\}=\{b\},$
color $6$ if $X\cap\{a,b,c\}\subseteq\{c\}.$
This proper $6$-coloring shows that $\chi(G_n)\le6.$

  • $\begingroup$ Thanks, but how to prove 5 colors is not sufficient :D $\endgroup$ – Ypical Jul 18 '16 at 20:19
  • $\begingroup$ I don't know... $\endgroup$ – bof Jul 18 '16 at 20:31

Your Answer

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

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