OBM 2003 Problem 6

Um grafo cujo conjunto de vértices $V$ tem $n$ elementos é bacana se existir um conjunto $D\subset \mathbb{N}$ e uma função injetiva $f:V\to \left[1, n^2/4\right]\cap \mathbb{N}$ tal que os vértices $p$ e $q$ são ligados por uma aresta se e somente se $|f(p)-f(q)|\in D$.

Mostre que existe $n_0\in \mathbb{N}$ tal que para todo $n\geq n_0$ existem grafos com $n$ vértices que não são bacanas.

Observação: Um grafo com conjunto de vértices $V$ é um par $(V, E)$ onde $E$ é um conjunto de subconjuntos de $V$, todos com exatamente dois elementos. Um conjunto $\{p, q\}$ é chamado de aresta se pertencer a $E$ e neste caso dizemos que esta aresta liga os vértices $p$ e $q$.