Um grafo cujo conjunto de vértices V tem n elementos é bacana se existir um conjunto D ⊂ N e uma função injetiva f :V ➝[1, n²/4]⋂ N tal que os vértices p e q são ligados por uma aresta se e somente se f ( p) - f (q) ∈ D.
Mostre que existe n₀ ∈ N tal que para todo n ≥ n₀ 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.