Mostrar el gráfico es regular

Question

<blockquote> <p>Si $G$ es un gráfico finito conectado que tiene no hay triángulos y $G$ tiene la propiedad de que si dos vértices tienen un vecino común entonces tienen exactamente dos vecinos comunes, ¿$G$ tiene que ser fuertemente regular?</p> </blockquote> <p><strong>Nota:</strong> ¿Mostró que es regular, pero cómo comprobar/refutar es fuertemente regular?</p>

Answer 1

La respuesta es "no". Un contraejemplo es proporcionado por el gráfico del hypercube $Q_n$ para cualquier $n\gt2$, en particular por el gráfico más cercano vecino de las esquinas de un cubo. Se cumplen las condiciones, pero algunos vértices no adyacentes tienen $2$ vecinos comunes mientras que otros tienen $0$.

Answer 2

Que u, v que dos vértices adyacentes. que v' ser vecino de v distinto de u, entonces u y v' tiene v vecino comun, por la condición debe existe otro vértice u 'que es adyacente a ambos u y v'. Por eso reitero este argumento a cada vecino de v (distinto de u) para obtener deg(u) no es menos que deg(v). Por simetría de u y v para obtener la otra dirección.