Generalización del Teorema de la Amistad en los gráficos?

Question

Si en un gráfico, cualquiera de los dos vértices tienen un número impar de común de los vecinos, es cierto que existe un vértice que es un 'universal amigo", me.e adyacente a todos los demás vértices?

(Se sabe que en ese caso el número de vértices que tiene que ser impar:

Demostrar que el grafo G con un número par de vértices tiene dos vértices con un número par de común prójimo )

Si cada uno de los números impares en la pregunta 1, entonces esta es la declaración de la Amistad teorema.

Answer 1

Como contraejemplo, considere la posibilidad de la Kneser gráfico de $K(6,2)$: su vértice conjunto se compone de todos los $15$ subconjuntos de a $\{1,2,3,4,5,6\}$ del tamaño de la $2$, y dos vértices están conectados siempre que corresponden a distintos subconjuntos.

A continuación, cualquiera de los dos no adyacentes vértices tienen $3$ común de los vecinos: por ejemplo, $\{1,2\}$ $\{1,3\}$ han común de los vecinos $\{4,5\}$, $\{4,6\}$, y $\{5,6\}$. Cualquiera de los dos vértices adyacentes tienen $1$ común vecino: por ejemplo, $\{1,2\}$ $\{3,4\}$ han común vecino $\{5,6\}$.

Sin embargo, no hay ningún vértice adyacente a todos los demás vértices; de hecho, $K(6,2)$ es regular de grado $6$.

(Kneser gráficos son a menudo un buen contraejemplos para las cosas; el gráfico de Petersen, que es $K(5,2)$, es el más popular de estos. Sin embargo, en este caso, he de reconocer que la acabo de buscar todos los gráficos en Mathematica la base de datos hasta que encontré uno con esta propiedad.)