Il Grafo con la G maiuscola

[Gerald Lambeau]

Direttamente dalle amene proposte di C1 Advanced.
Sia $k$ un intero positivo fissato. Determinare il minimo intero positivo $n \ge 5$ tale che esiste un Grafo con esattamente $n$ vertici e senza triangoli che possiede la seguente proprietà:
dati due vertici $A$ e $B$ non collegati, esistono esattamente altri $k$ vertici che sono collegati sia a $A$ che a $B$.