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.
$n>3$
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?
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.$