En un grafo simple $G$ , llamamos a $t$ vértices adyacentes por pares una $t$ -clique . Si un vértice está conectado con todos los demás vértices en el grafo, lo llamamos un vértice central. Dados dos enteros $n,k$ tales que $\dfrac {3}{2} \leq \dfrac{1}{2} n < k < n$ . Sea $G$ un grafo en $n$ vértices tal que (1) $G$ no contiene una $(k+1)$ - clique ; (2) si agregamos una arista arbitraria a $G$ , eso crea una $(k+1)$ - clique . Encuentra el menor número posible de vértices centrales en $G$ .