Here is the statement I'm trying to prove:
For $n = 2^m+1$, consider the graph on the pairs of integers $(i, j)$ with $1< i < j < n$ and edges between $(i, j)$ and $(k, l)$ if $j =k$.
Prove that the chromatic number is at least $m$.
I tried to do it by induction by finding some vertex that is connected to all (or enough) vertices of the graph for $m-1$, but didn't succeed. I tried to find some structure, but I really don't know what to look for.
Let me know if you have some ideas!
Thank you