So, I'm trying to solve the following exercise available in the book "The Probabilistic Method", by Alon and Spencer.
The Hajós number of a graph $G$ is the maximum number $k$ such that there are $k$ vertices in $G$ with a path between each pair so that all the $\binom{k}{2}$ paths are internally vertex disjoint (and no vertex is an internal vertex of a path and an endpoint of another). Is there a graph whose chromatic number exceeds twice its Hajós number?
My thoughts: I tried to follow this answer: Hajós Number vs. Chromatic Number
Following the hint, using the random graph $G(n, \frac{1}{2})$, it seems to me that there is a graph such that the Hajós number should be less or equal to $2 \sqrt{n}$, because for $k$ larger one would need more than $n$ vertices to construct $\binom{k}{2}$ such paths. My problem is how to get a lower bound for the chromatic number in this case. I'd appreciate any hint.
The chromatic number of a random graph is well-known. If you are not happy simply citing Theorem 10.3.1 of Alon and Spencer for the result that with high probability $$ \chi(G_{n,1/2}) \sim \frac{n}{2\log_2 n} $$ then we can get a lower bound of this order without too much difficulty. The probability that a set of $k$ vertices is independent is $2^{-k(k-1)/2}$, so the expected number of independent sets of size $k$ is $$ \binom nk 2^{-k(k-1)/2} \le \left(\frac{ne}{k} \cdot 2^{-(k-1)/2}\right)^k $$ and when $k = 2 \log_2 n$, this becomes $\left(\frac{e\sqrt 2}{k}\right)^k = o(1)$. So with high probability there are no independent sets of this size, and therefore we need at least $\frac{n}{2\log_2 n}$ colors, since each color can be used on at most $2\log_2 n$ vertices.