Considere la gráfica de $\overline G$, el gráfico con el mismo vértice establecer como $G$ y el conjunto de borde definido por: $u$ $v$ están conectados en $\overline G$ si y sólo si no son adyacentes en $G$. Entonces la propiedad
$$\text{For any $n$ vertices $v_1,\ldots,v_n$ in $G$, one vertex $v_1$ is adjacent to all of $v_2,\ldots,v_n$}\tag 1$$
es equivalente a
$$\text{For any $n$ vertices $v_1,\ldots,v_n$ in $\overline G$, one vertex $v_1$ is not adjacent to any of $v_2,\ldots,v_n$.}\tag 2$$
Reivindicación 1. Al $n$ es incluso, $(2)$ mantiene si y sólo si hay al menos $n+1$ vértices de grado $0$.
$(\Rightarrow)$ Supongamos, por una contradicción que hay en la mayoría de las $n$ vértices de grado $0$, entonces hay al menos $n$ vértices de grado $1$ o más. Considerar el subgrafo $H$ $\overline G$ inducida por la $k\ge n$ vértices de grado positivo. Si $k=n$ a continuación, se realiza desde la propiedad $(2)$ no puede mantener para estos $n$ vértices. Así que supongamos $k>n$; ahora puedo eliminar vértices de $H$ como se describe a continuación, en cada etapa no tenemos ningún vértices de $H$ con grado de $0$ en el subgrafo inducido. Si no está conectado a un componente de $H$ de los impares tamaño, eliminar un vértice de grado $1$, si puede ser encontrado; de lo contrario eliminar un vértice arbitrario-si la eliminación de un vértice $u_1$$\mathrm{deg}\, u_2=0$, $u_2$ tenía grado $1$ antes de la extracción. Si el más pequeño de componentes conectados de $H$ tiene el tamaño de $2$ y todos los componentes conectados incluso han tamaño, a continuación, retire los más pequeños (desde $n$ es incluso, $k\ge n+2$ si no hay impar de componentes). Si el más pequeño de componentes conectados de $H$ es uniforme y tiene un tamaño mayor que $2$, eliminar un vértice de grado $1$, si puede ser encontrado; de lo contrario eliminar un vértice arbitrario-si la eliminación de un vértice $u_1$$\mathrm{deg}\, u_2=0$, $u_2$ tenía grado $1$ antes de la extracción. Repitiendo este procedimiento, podemos llegar a un punto donde $H$ tiene el tamaño de $n$ y no aislado de vértices, es decir, $(2)$ no puede ser satisfecho.
$(\Leftarrow)$ Cualquier elección de $n$ vértices de $\overline G$ debe contener uno de los vértices de grado $0$, de los cuales hay $n+1$ (principio del palomar).
Reivindicación 2. Al $n$ es impar, $(2)$ mantiene si y sólo si hay al menos $n+1$ vértices de grado $0$, o sin vértices de grado $2$ o más.
$(\Rightarrow)$ Razón como antes, por la contradicción, para obtener el subgrafo $H$ $\overline G$ inducida por la $k\ge n$ vértices de grado positivo. Si $k=n$ hemos terminado, así que supongamos $k>n$. Considerar el componente conectado a $C$ $H$ que contiene el vértice $v$ de grado de al menos $2$. Si $C$ tiene incluso el tamaño de la $|C|\ge 4$, luego de eliminar un vértice de grado $1$, si puede ser encontrado; de lo contrario eliminar un vértice arbitrario. Por lo tanto, podemos suponer que la $C$ tiene impar tamaño, decir $|C|=m\ge 3$, y no aislado vértices. Llamar al resto $H^\prime=\overline G-C$ menos de la mencionada eliminado vértice-si es aplicable. De la misma manera como antes, recortar $H^\prime$ hacia abajo hasta que tenga el tamaño de la $k^\prime=n-m$, en cada etapa de la priorización de los impares del tamaño de los componentes conectados, a continuación, los componentes de tamaño $2$, mayor incluso del tamaño de los componentes. (Tenga en cuenta que si no hay impar de componentes de $H^\prime$, el componente más pequeño es el tamaño de la $2$, e $|H^\prime|>n-m$, entonces a partir de la $|H^\prime|$ $n-m$ son ambos inclusive, el componente más pequeño se puede quitar de forma segura mientras que la preservación de la desigualdad de $|H^\prime|\ge n-m$.) Una vez hecho esto, $H^\prime+C$ tiene el tamaño de $n$ y no aislado vértices, por lo que la propiedad $(2)$ no puede mantener.
$(\Leftarrow)$ Si $\overline G$ no tiene ningún vértice de grado $2$ o más, entonces es una colección de $K_2$s y $K_1$s. Desde $n$ es impar, la elección de la $n$ vértices tiene un vértice que es en su propio componente conectado. Si hay un vértice de grado $2$ o más, como el de la reivindicación de uno, la elección de la $n$ vértices de $\overline G$ debe contener uno de los vértices de grado $0$
Los límites de las propiedades. Un mínimo vinculado $M$ en el número de aristas para satisfacer $(1)$ es un límite superior en el número de aristas que puede satisfacer $(2)$.
Al $n$ es aún, por lo menos $n+1$ vértices deben ser grado $0$; incluyendo todas las posibles aristas en el resto de $n-1$ vértices da $\tfrac 12(n-1)(n-2)$ bordes. Al $n$ es impar, se puede hacer mejor cuando $n=1$, $n=3$ o $n=5$: un gráfico con ningún vértice de grado $2$ o más (en el mejor), una colección de $K_2$s, y ha $n$ bordes. A continuación, $M$ es la diferencia entre el $\tfrac 12(2n)(2n-1)$ y estos números. Por lo tanto
$$M=\begin{cases}
2n^2-2n&\text{%#%#%, %#%#% or %#%#%},\\
\tfrac 12(3n^2+n-2)&\text{otherwise}.
\end{casos}$$
Observación. También es posible trabajar directamente con la propiedad $n=1$. Observe que (excluyendo los casos especiales $n=3$, $n=5$, $(1)$) los gráficos que cumplan los mínimos obligados son gráficos de split de a $n=1$ vértices con clique de tamaño $3$ y un conjunto independiente de tamaño $5$. El número de aristas en los gráficos de este tipo es $2n$$
El punto crucial aquí es que la elección de la $n+1$ vértices se cruza con la de la camarilla, por lo tanto, contiene un vértice adyacente a las otras $n-1$ vértices. No podemos mejorar en esta obligado, debido a la eliminación de un borde de $$(2n-1)+(2n-2)+\cdots+(n-1).$ de la camarilla de producir un conjunto $n$ (donde $n-1$ son del conjunto independiente) que no satisface $u_1u_2$. Desde $\{u_1,u_2,v_3,\ldots,v_n\}$ forman un conjunto independiente, que no puede ser el 'especial' vértice adyacente a la de los demás. Ni puede $v_3,\ldots,v_n$ $(1)$ tienen la propiedad-que no son adyacentes el uno al otro!
Se necesitaría un poco de trabajo para demostrar que esta es una formulación óptima de todos los $v_3,\ldots,v_n$ excepto $u_1$ ,$u_2$ y $n$ (no estoy seguro de cómo hacerlo).
