The Hajós number of a graph $G$ is the largest $k$ such that there are $k$ vertices in $G$ with a path between each pair so that all $k \choose 2$ paths are internally pairwise vertex disjoint (i.e. if a vertex is not one of the $k$, then it appears on at most one such path), and none of the $k$ vertices is an internal vertex of any of the paths. Is there a graph whose chromatic number exceeds twice its Hajos number?
The problem is from the book Probabilistic Methods by Noga Alon.
Hint: Consider $G(n,\frac{1}{2})$
Every set contains almost half of edges $w.h.p.$
So you need at least one vertex for almost half on $k\choose2$ which is greater than total number of vertices if $k$ is large enough.