Sea un gráfico simple en n vértices ( n > 3 ) sin vértices de grado n - 1 . Suponga que para cualquiera de los dos vértices de G , hay un vértice único adyacente a ambos. Es un ejercicio de A Course in Combinatorics , van Lint y Wilson, para demostrar que dicho gráfico es regular.
Sin embargo, mi pregunta es si existen gráficos que satisfagan las restricciones dadas. Mientras discutía el ejercicio original durante una sesión de resolución de problemas, alguien preguntó si podríamos encontrar un ejemplo de un gráfico donde cada par de vértices tenga un vecino común único, y no haya vértices globales. Tampoco pudimos encontrar un ejemplo o procedimiento concreto para la construcción, ni establecimos una prueba de que ningún gráfico tiene estas propiedades.
¿Alguna sugerencia?
Nota: en cuanto a probar que dicho gráfico es regular, resulta ser bastante sencillo, la idea aproximada es emparejar a los vecinos de cada par de vértices utilizando los criterios únicos de vecino común para establecer el hecho de que cada par de los vértices tienen el mismo grado, y luego un argumento de transitividad, con la ayuda de la restricción no-global-vertex, nos da que el gráfico es regular.
fuente