Grafos sem \(C_4\)

Quantas arestas pode ter um grafo sem que ele contenha um circuito com quatro vértices (\(C_4\))?

Spoiler alert! Vale a pena pensar neste problema antes de ler a discussão abaixo.

Um \(C_4\) é o grafo conexo com 4 vértices, cada um com dois vizinhos. Num grafo sem \(C_4\), cada par de vértices tem no máximo um vizinho comum. Considere o grafo formado por \(k\) cópias de \(K_2\) (grafo completo com dois vértices), em que acrescentamos um vértice novo \(v\) e arestas ligando cada um dos demais vértices a \(v\). Esse grafo é tal que qualquer par de vértices possui um vizinho em comum, e possui \(3k\) arestas.

Outro comentário: num grafo em que cada par de vértices possui um vizinho comum, qualquer nova aresta gera um \(C_4\). (e, se há ao menos 5 vértices, um \(C_5\) também).

Pergunta: o número de arestas de um grafo \(G\) com \(n\) vértices e tal que todo par de vértices possui exatamente um vizinho em comum é único para cada \(n\) fixo?

Para pensar: seja \(G\) um grafo livre de \(C_4\) que possui vértices \(u\) e \(v\) sem vizinhança comum — isto é, \(N(u)\cap N(v)=\varnothing\). É possível que ele seja máximo (no número de arestas)? Em outras palavras, estamos certos de que não existe grafo com mais arestas do que \(G\) e que seja livre de \(C_4\)?